diff --git a/storage/client.go b/storage/client.go
new file mode 100644
index 0000000..09f5925
--- /dev/null
+++ b/storage/client.go
@@ -0,0 +1,100 @@
+// Copyright 2017 The Go 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 storage contains a client for the performance data storage server.
+package storage
+
+import (
+	"io"
+	"net/http"
+	"net/url"
+
+	"golang.org/x/perf/storage/benchfmt"
+)
+
+// A Client issues queries to a performance data storage server.
+// It is safe to use from multiple goroutines simultaneously.
+type Client struct {
+	// BaseURL is the base URL of the storage server.
+	BaseURL string
+	// HTTPClient is the HTTP client for sending requests. If nil, http.DefaultClient will be used.
+	HTTPClient *http.Client
+}
+
+// httpClient returns the http.Client to use for requests.
+func (c *Client) httpClient() *http.Client {
+	if c.HTTPClient != nil {
+		return c.HTTPClient
+	}
+	return http.DefaultClient
+}
+
+// Query searches for results matching the given query string.
+//
+// The query string is first parsed into quoted words (as in the shell)
+// and then each word must be formatted as one of the following:
+// key:value - exact match on label "key" = "value"
+// key>value - value greater than (useful for dates)
+// key<value - value less than (also useful for dates)
+func (c *Client) Query(q string) *Query {
+	hc := c.httpClient()
+
+	resp, err := hc.Get(c.BaseURL + "/search?" + url.Values{"q": []string{q}}.Encode())
+	if err != nil {
+		return &Query{err: err}
+	}
+
+	br := benchfmt.NewReader(resp.Body)
+
+	return &Query{br: br, body: resp.Body}
+}
+
+// A Query allows iteration over the results of a search query.
+// Use Next to advance through the results, making sure to call Close when done:
+//
+//   q := client.Query("key:value")
+//   defer q.Close()
+//   for q.Next() {
+//     res := q.Result()
+//     ...
+//   }
+//   if err = q.Err(); err != nil {
+//     // handle error encountered during query
+//   }
+type Query struct {
+	br   *benchfmt.Reader
+	body io.ReadCloser
+	err  error
+}
+
+// Next prepares the next result for reading with the Result
+// method. It returns false when there are no more results, either by
+// reaching the end of the input or an error.
+func (q *Query) Next() bool {
+	if q.err != nil {
+		return false
+	}
+	return q.br.Next()
+}
+
+// Result returns the most recent result generated by a call to Next.
+func (q *Query) Result() *benchfmt.Result {
+	return q.br.Result()
+}
+
+// Err returns the first error encountered during the query.
+func (q *Query) Err() error {
+	if q.err != nil {
+		return q.err
+	}
+	return q.br.Err()
+}
+
+// Close frees resources associated with the query.
+func (q *Query) Close() error {
+	q.body.Close()
+	return q.err
+}
+
+// TODO(quentin): Move upload code here from cmd/benchsave?
diff --git a/storage/client_test.go b/storage/client_test.go
new file mode 100644
index 0000000..c05ad20
--- /dev/null
+++ b/storage/client_test.go
@@ -0,0 +1,82 @@
+// Copyright 2017 The Go 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 storage
+
+import (
+	"bytes"
+	"fmt"
+	"io/ioutil"
+	"net/http"
+	"net/http/httptest"
+	"os"
+	"os/exec"
+	"testing"
+
+	"golang.org/x/perf/storage/benchfmt"
+)
+
+func TestQuery(t *testing.T) {
+	ts := httptest.NewServer(http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
+		if have, want := r.URL.RequestURI(), "/search?q=key1%3Avalue+key2%3Avalue"; have != want {
+			t.Errorf("RequestURI = %q, want %q", have, want)
+		}
+		fmt.Fprintf(w, "key: value\nBenchmarkOne 5 ns/op\nkey: value2\nBenchmarkTwo 10 ns/op\n")
+	}))
+	defer ts.Close()
+
+	c := &Client{BaseURL: ts.URL}
+
+	q := c.Query("key1:value key2:value")
+	defer q.Close()
+
+	var buf bytes.Buffer
+	bp := benchfmt.NewPrinter(&buf)
+
+	for q.Next() {
+		if err := bp.Print(q.Result()); err != nil {
+			t.Fatalf("Print: %v", err)
+		}
+	}
+	if err := q.Err(); err != nil {
+		t.Fatalf("Err: %v", err)
+	}
+	want := "key: value\nBenchmarkOne 5 ns/op\nkey: value2\nBenchmarkTwo 10 ns/op\n"
+	if diff := diff(buf.String(), want); diff != "" {
+		t.Errorf("wrong results: (- have/+ want)\n%s", diff)
+	}
+}
+
+// diff returns the output of unified diff on s1 and s2. If the result
+// is non-empty, the strings differ or the diff command failed.
+func diff(s1, s2 string) string {
+	f1, err := ioutil.TempFile("", "benchfmt_test")
+	if err != nil {
+		return err.Error()
+	}
+	defer os.Remove(f1.Name())
+	defer f1.Close()
+
+	f2, err := ioutil.TempFile("", "benchfmt_test")
+	if err != nil {
+		return err.Error()
+	}
+	defer os.Remove(f2.Name())
+	defer f2.Close()
+
+	f1.Write([]byte(s1))
+	f2.Write([]byte(s2))
+
+	data, err := exec.Command("diff", "-u", f1.Name(), f2.Name()).CombinedOutput()
+	if len(data) > 0 {
+		// diff exits with a non-zero status when the files don't match.
+		// Ignore that failure as long as we get output.
+		err = nil
+	}
+	if err != nil {
+		data = append(data, []byte(err.Error())...)
+	}
+	return string(data)
+
+}