diff --git a/catapult/cmd/catapult/add_diagnostics.go b/catapult/cmd/catapult/add_diagnostics.go
deleted file mode 100644
index c59519c..0000000
--- a/catapult/cmd/catapult/add_diagnostics.go
+++ /dev/null
@@ -1,34 +0,0 @@
-// Copyright 2017 The Fuchsia Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file
-
-package main
-
-import (
-	"context"
-	"flag"
-	"log"
-
-	"github.com/google/subcommands"
-)
-
-type AddDiagnosticsCommand struct{}
-
-func (*AddDiagnosticsCommand) Name() string {
-	return "add_diagnostics"
-}
-
-func (*AddDiagnosticsCommand) Usage() string {
-	return "add_diagnostics"
-}
-
-func (*AddDiagnosticsCommand) Synopsis() string {
-	return "Adds diagnostics to a HistogramSet"
-}
-
-func (*AddDiagnosticsCommand) SetFlags(flags *flag.FlagSet) {}
-
-func (*AddDiagnosticsCommand) Execute(ctx context.Context, f *flag.FlagSet, _ ...interface{}) subcommands.ExitStatus {
-	log.Println("Unimplemented: AddDiagnostics")
-	return subcommands.ExitFailure
-}
diff --git a/catapult/diagnostic.go b/catapult/diagnostic.go
new file mode 100644
index 0000000..c30103f
--- /dev/null
+++ b/catapult/diagnostic.go
@@ -0,0 +1,31 @@
+// Copyright 2018 The Fuchsia Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file
+
+package catapult
+
+// Types of Catapult Diagnostics.
+//
+// Every Diagnostic must have a Type value from this list.  For a list of all
+// Diagnostic types, see:
+// https://github.com/catapult-project/catapult/blob/master/docs/histogram-set-json-format.md#diagnostics
+const (
+	DiagnosticTypeGenericSet = "GenericSet"
+)
+
+// Diagnostic is an interface for Catapult Diagnostics.
+type Diagnostic interface {
+	// GetGUID returns the GUID of this diagnostic.
+	GetGUID() string
+}
+
+// GenericSetDiagnostic stores arbitary untyped data in Histograms.
+type GenericSetDiagnostic struct {
+	Type   string   `json:"type"`
+	GUID   string   `json:"guid"`
+	Values []string `json:"values"`
+}
+
+func (d *GenericSetDiagnostic) GetGUID() string {
+	return d.GUID
+}
diff --git a/catapult/histogram.go b/catapult/histogram.go
index f5719e0..5e82509 100644
--- a/catapult/histogram.go
+++ b/catapult/histogram.go
@@ -1,4 +1,4 @@
-// Copyright 2017 The Fuchsia Authors. All rights reserved.
+// Copyright 2018 The Fuchsia Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file
 
@@ -6,6 +6,7 @@
 
 import (
 	"fmt"
+	"log"
 	"math"
 
 	schema "fuchsia.googlesource.com/testing/perf/schema/v1"
@@ -25,27 +26,50 @@
 //   AllBins
 //   SummaryOptions
 type Histogram struct {
-	Name               string            `json:"name"`
-	GUID               string            `json:"guid"`
-	Unit               string            `json:"unit"`
-	Description        string            `json:"description"`
-	Diagnostics        map[string]string `json:"diagnostics"`
-	SampleValues       []float64         `json:"sampleValues"`
-	MaxNumSampleValues int               `json:"maxNumSampleValues"`
-	NumNans            int               `json:"numNans"`
-	Running            []float64         `json:"running"`
+	Name               string    `json:"name"`
+	GUID               string    `json:"guid"`
+	Unit               string    `json:"unit"`
+	Description        string    `json:"description"`
+	SampleValues       []float64 `json:"sampleValues"`
+	MaxNumSampleValues int       `json:"maxNumSampleValues"`
+	NumNans            int       `json:"numNans"`
+	Running            []float64 `json:"running"`
+	// Diagnostics maps a Diagnostic's name to its GUID.
+	//
+	// These map entries communicate that the diagnostic with the given
+	// name and GUID contains metadata that can help debug regressions and
+	// other issues with this Histogram in the Catapult Dashboard.
+	Diagnostics map[string]string `json:"diagnostics"`
 }
 
-// ConvertVariantsToHistograms converts a collection of Fuchsia benchmark variants into
-// a list of Catapult Histograms.
-func ConvertVariantsToHistograms(variants []schema.Variant) []Histogram {
-	var histogramSet []Histogram
+// AddDiagnostic associates name with the given GUID in this Histogram's
+// Diagnostics map.
+//
+// If the the new entry overwrites an existing entry, a warning is logged.
+func (h *Histogram) AddDiagnostic(name string, guid string) {
+
+	if h.Diagnostics == nil {
+		h.Diagnostics = make(map[string]string)
+	}
+
+	if existing, ok := h.Diagnostics[name]; ok && existing != guid {
+		log.Printf(
+			"Overwriting shared Diagnostic %v in Histogram %v."+
+				"($old, $new) = (%v, %v)",
+			name, h.Name, existing, guid)
+	}
+
+	h.Diagnostics[name] = guid
+}
+
+// ConvertVariantsToHistograms converts a collection of Fuchsia benchmark
+// variants into a list of Catapult Histograms.
+func ConvertVariantsToHistograms(variants []schema.Variant) HistogramSet {
+	histogramSet := HistogramSet{}
 	for _, variant := range variants {
 		for _, benchmarkData := range variant.FBenchmarksData {
-			histogramSet = append(
-				histogramSet,
-				createHistogram(variant, benchmarkData),
-			)
+			histogramSet.AddHistogram(
+				createHistogram(variant, benchmarkData))
 		}
 	}
 
diff --git a/catapult/histogram_set.go b/catapult/histogram_set.go
new file mode 100644
index 0000000..1a6f2c6
--- /dev/null
+++ b/catapult/histogram_set.go
@@ -0,0 +1,62 @@
+// Copyright 2018 The Fuchsia Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file
+
+package catapult
+
+import (
+	"errors"
+)
+
+// HistogramSet is a collection of Histograms and related Diagnostics.
+type HistogramSet struct {
+	histograms  []Histogram
+	diagnostics []Diagnostic
+}
+
+// AddHistogram adds a histogram to this HistogramSet.
+//
+// If this HistogramSet already contains a Diagnostic, the addition fails and
+// an error is returned.
+//
+// TODO(kharland): This API does not allow adding a Histogram after Diagnostics
+// have been added because it is not clear if the caller intended for the new
+// Histogram to contain the same references to the shared Diagnostics in this
+// HistogramSet as the existing Histograms. Allow adding Histograms after
+// Diagnostics when Fuchsia needs this functionality.
+func (h *HistogramSet) AddHistogram(histogram Histogram) error {
+	if len(h.diagnostics) > 0 {
+		return errors.New("can't add Histogram after adding Diagnostics")
+	}
+	h.histograms = append(h.histograms, histogram)
+	return nil
+}
+
+// AddSharedDiagnostic adds a diagnostic to this HistogramSet.
+//
+// A shared Diagnostic is a diagnostic that exists in the HistogramSet, so
+// that it may be referenced by Histograms within the set. A reference to the
+// Diagnostic is automatically added to each Histogram in the set when calling
+// this method. name is used as the key for this reference.
+func (h *HistogramSet) AddSharedDiagnostic(name string, diagnostic Diagnostic) {
+	h.diagnostics = append(h.diagnostics, diagnostic)
+
+	guid := diagnostic.GetGUID()
+
+	// Reference the diagnostic's GUID in each Histogram in this set.
+	for _, histogram := range h.histograms {
+		histogram.AddDiagnostic(name, guid)
+	}
+}
+
+// ToJSON implements the HistogramSet interface.
+func (h *HistogramSet) ToJSON() []interface{} {
+	jsonObject := []interface{}{}
+	for _, entry := range h.histograms {
+		jsonObject = append(jsonObject, entry)
+	}
+	for _, entry := range h.diagnostics {
+		jsonObject = append(jsonObject, entry)
+	}
+	return jsonObject
+}
diff --git a/catapult/histogram_set_test.go b/catapult/histogram_set_test.go
new file mode 100644
index 0000000..aa93e5a
--- /dev/null
+++ b/catapult/histogram_set_test.go
@@ -0,0 +1,134 @@
+// Copyright 2018 The Fuchsia Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file
+package catapult_test
+
+import (
+	"reflect"
+	"testing"
+
+	"fuchsia.googlesource.com/testing/catapult"
+	"github.com/kr/pretty"
+)
+
+func TestAddHistogram(t *testing.T) {
+	t.Run("When the HistogramSet is empty", func(t *testing.T) {
+		histogramSet := catapult.HistogramSet{}
+		histogram := catapult.Histogram{Name: "test_histogram"}
+
+		expectedJSON := []interface{}{histogram}
+		histogramSet.AddHistogram(histogram)
+
+		if !reflect.DeepEqual(histogramSet.ToJSON(), expectedJSON) {
+			t.Errorf("Invalid HistogramSet. Got %+v. Expected %+v",
+				pretty.Sprint(histogramSet.ToJSON()),
+				pretty.Sprint(expectedJSON),
+			)
+		}
+	})
+
+	t.Run("When the HistogramSet contains other Histograms", func(t *testing.T) {
+		histogramSet := catapult.HistogramSet{}
+		histogram1 := catapult.Histogram{Name: "test_histogram_1"}
+		histogram2 := catapult.Histogram{Name: "test_histogram_2"}
+
+		expectedJSON := []interface{}{histogram1, histogram2}
+
+		histogramSet.AddHistogram(histogram1)
+		histogramSet.AddHistogram(histogram2)
+		if !reflect.DeepEqual(histogramSet.ToJSON(), expectedJSON) {
+			t.Errorf("Invalid HistogramSet. Got %+v. Expected %+v",
+				pretty.Sprint(histogramSet.ToJSON()),
+				pretty.Sprint(expectedJSON),
+			)
+		}
+	})
+
+	t.Run("When the HistogramSet contains other Diagnostics", func(t *testing.T) {
+		histogramSet := catapult.HistogramSet{}
+		histogram := catapult.Histogram{
+			Name:        "test_histogram",
+			Diagnostics: make(map[string]string),
+		}
+		diagnostic := &catapult.GenericSetDiagnostic{
+			Type:   catapult.DiagnosticTypeGenericSet,
+			Values: []string{"test_value"},
+			GUID:   "test_guid",
+		}
+
+		// Should return an error without modifying the HistogramSet
+		// because all Histograms must be added before any Diagnotics
+		// are added.
+		expectedJSON := []interface{}{diagnostic}
+		histogramSet.AddSharedDiagnostic("test_diagnostic", diagnostic)
+		if histogramSet.AddHistogram(histogram) == nil {
+			t.Errorf("expected an error when adding a Histogram after a Diagnostic")
+		}
+
+		if !reflect.DeepEqual(histogramSet.ToJSON(), expectedJSON) {
+			t.Errorf("Invalid HistogramSet. Got %+v. Expected %+v",
+				pretty.Sprint(histogramSet.ToJSON()),
+				pretty.Sprint(expectedJSON),
+			)
+		}
+	})
+}
+
+func TestAddSharedDiagnostic(t *testing.T) {
+	t.Run("When there are no Histograms in the set", func(t *testing.T) {
+		diagnostic := &catapult.GenericSetDiagnostic{
+			Type:   catapult.DiagnosticTypeGenericSet,
+			GUID:   "test_guid",
+			Values: []string{"test_value"},
+		}
+		histogramSet := catapult.HistogramSet{}
+		histogramSet.AddSharedDiagnostic("test_diagnostic", diagnostic)
+
+		expectedJSON := []interface{}{diagnostic}
+		if !reflect.DeepEqual(histogramSet.ToJSON(), expectedJSON) {
+			t.Errorf("Invalid HistogramSet. Got: %+v\nExpected: %+v",
+				pretty.Sprint(histogramSet.ToJSON()),
+				pretty.Sprint(expectedJSON))
+		}
+
+	})
+
+	t.Run("When there are existing Histograms in the set", func(t *testing.T) {
+		diagnostic := &catapult.GenericSetDiagnostic{
+			Type:   catapult.DiagnosticTypeGenericSet,
+			GUID:   "test_guid",
+			Values: []string{"test_value"},
+		}
+
+		histogramSet := catapult.HistogramSet{}
+		histogramSet.AddHistogram(catapult.Histogram{
+			Name:        "test_histogram_1",
+			Diagnostics: make(map[string]string),
+		})
+		histogramSet.AddHistogram(catapult.Histogram{
+			Name:        "test_histogram_2",
+			Diagnostics: make(map[string]string),
+		})
+		histogramSet.AddSharedDiagnostic("test_diagnostic", diagnostic)
+
+		// Each histogram in the set should have a reference to the diagnostic in its
+		// Diagnostics map.
+		expectedJSON := []interface{}{
+			catapult.Histogram{
+				Name:        "test_histogram_1",
+				Diagnostics: map[string]string{"test_diagnostic": "test_guid"},
+			},
+			catapult.Histogram{
+				Name:        "test_histogram_2",
+				Diagnostics: map[string]string{"test_diagnostic": "test_guid"},
+			},
+			diagnostic,
+		}
+
+		if !reflect.DeepEqual(histogramSet.ToJSON(), expectedJSON) {
+			t.Errorf("Invalid HistogramSet. Got: %+v\nExpected: %+v",
+				pretty.Sprint(histogramSet.ToJSON()),
+				pretty.Sprint(expectedJSON))
+		}
+	})
+}
diff --git a/catapult/histogram_test.go b/catapult/histogram_test.go
index 7beab79..3e27da0 100644
--- a/catapult/histogram_test.go
+++ b/catapult/histogram_test.go
@@ -1,3 +1,6 @@
+// Copyright 2018 The Fuchsia Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file
 package catapult_test
 
 import (
@@ -8,6 +11,7 @@
 	schema "fuchsia.googlesource.com/testing/perf/schema/v1"
 	"github.com/stretchr/testify/assert"
 	"github.com/stretchr/testify/suite"
+	"reflect"
 )
 
 type HistogramTestSuite struct {
@@ -18,6 +22,8 @@
 	suite.Run(t, new(HistogramTestSuite))
 }
 
+// TODO(kjharland): After writing this test the team decided we shouldn't use
+//  assertion libraries. Remove `assert.*` references in a later change.
 func (s *HistogramTestSuite) TestConvertVariantsToHistograms() {
 	var perfTestOutput = []byte(`{
 			"variants": [{
@@ -42,9 +48,19 @@
 
 	json.Unmarshal(perfTestOutput, &variants)
 	histogramSet := ConvertVariantsToHistograms(variants.Variants)
-	histogram := histogramSet[0]
 
-	assert.Equal(s.T(), len(histogramSet), 1)
+	// TODO(kjharland): ConvertVariantsToHistograms should just return a list of
+	// Histograms. Fix and delete this type-check
+	histogramSetJSON := histogramSet.ToJSON()
+	assert.Equal(s.T(), len(histogramSetJSON), 1)
+
+	histogram, ok := histogramSetJSON[0].(Histogram)
+	if !ok {
+		s.T().Errorf(
+			"HistogramSet entry is not a Histogram. Object has type: %T",
+			histogramSetJSON[0])
+	}
+
 	assert.Equal(s.T(), histogram.Name, "example_variant, example_benchmark_data")
 	assert.Len(s.T(), histogram.GUID, 36)
 	assert.Equal(s.T(), histogram.Unit, "ms_smallerIsBetter")
@@ -69,3 +85,55 @@
 		2.5e-10,               // variance
 	})
 }
+
+func (s *HistogramTestSuite) TestHistogram_AddDiagnostic() {
+	var testName, testGUID string
+	var histogram Histogram
+
+	setUp := func() {
+		testName = "test-name"
+		testGUID = "test-guid"
+		histogram = Histogram{}
+		histogram.AddDiagnostic(testName, testGUID)
+	}
+
+	s.T().Run("should do nothing if adding an identical name-guid pair", func(t *testing.T) {
+		setUp()
+		expectedDiagnostics := map[string]string{testName: testGUID}
+
+		histogram.AddDiagnostic(testName, testGUID)
+
+		if !reflect.DeepEqual(expectedDiagnostics, histogram.Diagnostics) {
+			s.T().Errorf("invalid diagnostics map. Expected %v. Got %v",
+				expectedDiagnostics, histogram.Diagnostics)
+		}
+	})
+
+	s.T().Run("should add a new name-guid pair when given a unique name.", func(t *testing.T) {
+		setUp()
+		expectedDiagnostics := map[string]string{
+			testName:         testGUID,
+			"different-name": testGUID,
+		}
+
+		histogram.AddDiagnostic("different-name", testGUID)
+
+		if !reflect.DeepEqual(expectedDiagnostics, histogram.Diagnostics) {
+			s.T().Errorf("invalid diagnostics map. Expected %v. Got %v",
+				expectedDiagnostics, histogram.Diagnostics)
+		}
+	})
+
+	s.T().Run("should overwrite an existing name-guid pair", func(t *testing.T) {
+		setUp()
+		expectedDiagnostics := map[string]string{
+			testName: "different-guid",
+		}
+
+		histogram.AddDiagnostic(testName, "different-guid")
+		if !reflect.DeepEqual(expectedDiagnostics, histogram.Diagnostics) {
+			s.T().Errorf("Diagnostics map was modified. Expected %v. Got %v",
+				expectedDiagnostics, histogram.Diagnostics)
+		}
+	})
+}