diff --git a/internal/format/format.go b/internal/format/format.go
index b7623d1..c70bc0f 100644
--- a/internal/format/format.go
+++ b/internal/format/format.go
@@ -29,3 +29,15 @@
 	// - user preferences, like measurement systems
 	// - options
 }
+
+// A Statement is a Var or an Expression.
+type Statement interface {
+	statement()
+}
+
+// A String a literal string format.
+type String string
+
+func (String) statement() {}
+
+// TODO: Select, Var, Case, StatementSequence
diff --git a/message/catalog.go b/message/catalog.go
new file mode 100644
index 0000000..41c31f4
--- /dev/null
+++ b/message/catalog.go
@@ -0,0 +1,113 @@
+// Copyright 2015 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 message
+
+// TODO: some types in this file will need to be made public at some time.
+// Documentation and method names will reflect this by using the exported name.
+
+import (
+	"sync"
+
+	"golang.org/x/text/internal"
+	"golang.org/x/text/internal/format"
+	"golang.org/x/text/language"
+)
+
+// DefaultCatalog is used by SetString.
+var DefaultCatalog *Catalog = newCatalog()
+
+// SetString calls SetString on the default Catalog.
+func SetString(tag language.Tag, key string, msg string) error {
+	return DefaultCatalog.SetString(tag, key, msg)
+}
+
+// TODO:
+// // SetSelect is a shorthand for DefaultCatalog.SetSelect.
+// func SetSelect(tag language.Tag, key string, s ...format.Statement) error {
+// 	return DefaultCatalog.SetSelect(tag, key, s...)
+// }
+
+type msgMap map[string]format.Statement
+
+// A Catalog holds translations for messages for supported languages.
+type Catalog struct {
+	index map[language.Tag]msgMap
+
+	mutex sync.Mutex // For locking all operations.
+}
+
+// Printer creates a Printer that uses c.
+func (c *Catalog) Printer(tag language.Tag) *Printer {
+	// TODO: pre-create indexes for tag lookup.
+	return &Printer{
+		tag: tag,
+		cat: c,
+	}
+}
+
+// NewCatalog returns a new Catalog. If a message is not present in a Catalog,
+// the fallback Catalogs will be used in order as an alternative source.
+func newCatalog(fallback ...*Catalog) *Catalog {
+	// TODO: implement fallback.
+	return &Catalog{
+		index: map[language.Tag]msgMap{},
+	}
+}
+
+// Languages returns a slice of all languages for which the Catalog contains
+// variants.
+func (c *Catalog) Languages() []language.Tag {
+	c.mutex.Lock()
+	defer c.mutex.Unlock()
+
+	tags := []language.Tag{}
+	for t, _ := range c.index {
+		tags = append(tags, t)
+	}
+	internal.SortTags(tags)
+	return tags
+}
+
+// SetString sets the translation for the given language and key.
+func (c *Catalog) SetString(tag language.Tag, key string, msg string) error {
+	return c.set(tag, key, format.String(msg))
+}
+
+func (c *Catalog) get(tag language.Tag, key string) (msg string, ok bool) {
+	c.mutex.Lock()
+	defer c.mutex.Unlock()
+
+	for ; ; tag = tag.Parent() {
+		if msgs, ok := c.index[tag]; ok {
+			if statement, ok := msgs[key]; ok {
+				// TODO: use type switches when we implement selecting.
+				msg := string(statement.(format.String))
+				return msg, true
+			}
+		}
+		if tag == language.Und {
+			break
+		}
+	}
+	return "", false
+}
+
+func (c *Catalog) set(tag language.Tag, key string, s ...format.Statement) error {
+	if len(s) != 1 {
+		// TODO: handle errors properly when we process statement sequences.
+		panic("statement sequence should be of length 1")
+	}
+
+	c.mutex.Lock()
+	defer c.mutex.Unlock()
+
+	m := c.index[tag]
+	if m == nil {
+		m = map[string]format.Statement{}
+		c.index[tag] = m
+	}
+	m[key] = s[0]
+	return nil
+}
diff --git a/message/catalog_test.go b/message/catalog_test.go
new file mode 100644
index 0000000..3b693c9
--- /dev/null
+++ b/message/catalog_test.go
@@ -0,0 +1,98 @@
+// Copyright 2015 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 message
+
+import (
+	"reflect"
+	"testing"
+
+	"golang.org/x/text/internal"
+	"golang.org/x/text/language"
+)
+
+type entry struct{ tag, key, msg string }
+
+var testCases = []struct {
+	desc   string
+	cat    []entry
+	lookup []entry
+}{{
+	desc: "empty catalog",
+	lookup: []entry{
+		{"en", "key", ""},
+		{"en", "", ""},
+		{"nl", "", ""},
+	},
+}, {
+	desc: "one entry",
+	cat: []entry{
+		{"en", "hello", "Hello!"},
+	},
+	lookup: []entry{
+		{"und", "hello", ""},
+		{"nl", "hello", ""},
+		{"en", "hello", "Hello!"},
+		{"en-US", "hello", "Hello!"},
+		{"en-GB", "hello", "Hello!"},
+		{"en-oxendict", "hello", "Hello!"},
+		{"en-oxendict-u-ms-metric", "hello", "Hello!"},
+	},
+}, {
+	desc: "hierarchical languages",
+	cat: []entry{
+		{"en", "hello", "Hello!"},
+		{"en-GB", "hello", "Hellø!"},
+		{"en-US", "hello", "Howdy!"},
+		{"en", "greetings", "Greetings!"},
+	},
+	lookup: []entry{
+		{"und", "hello", ""},
+		{"nl", "hello", ""},
+		{"en", "hello", "Hello!"},
+		{"en-US", "hello", "Howdy!"},
+		{"en-GB", "hello", "Hellø!"},
+		{"en-oxendict", "hello", "Hello!"},
+		{"en-US-oxendict-u-ms-metric", "hello", "Howdy!"},
+
+		{"und", "greetings", ""},
+		{"nl", "greetings", ""},
+		{"en", "greetings", "Greetings!"},
+		{"en-US", "greetings", "Greetings!"},
+		{"en-GB", "greetings", "Greetings!"},
+		{"en-oxendict", "greetings", "Greetings!"},
+		{"en-US-oxendict-u-ms-metric", "greetings", "Greetings!"},
+	},
+}}
+
+func initCat(entries []entry) (*Catalog, []language.Tag) {
+	tags := []language.Tag{}
+	cat := newCatalog()
+	for _, e := range entries {
+		tag := language.MustParse(e.tag)
+		tags = append(tags, tag)
+		cat.SetString(tag, e.key, e.msg)
+	}
+	return cat, internal.UniqueTags(tags)
+}
+
+func TestCatalog(t *testing.T) {
+	for _, tc := range testCases {
+		cat, wantTags := initCat(tc.cat)
+
+		// languages
+		if got := cat.Languages(); !reflect.DeepEqual(got, wantTags) {
+			t.Errorf("%s:Languages: got %v; want %v", tc.desc, got, wantTags)
+		}
+
+		// Lookup
+		for _, e := range tc.lookup {
+			tag := language.MustParse(e.tag)
+			msg, ok := cat.get(tag, e.key)
+			if okWant := e.msg != ""; ok != okWant || msg != e.msg {
+				t.Errorf("%s:Lookup(%s, %s) = %s, %v; want %s, %v", tc.desc, tag, e.key, msg, ok, e.msg, okWant)
+			}
+		}
+	}
+}
diff --git a/message/message.go b/message/message.go
index 22d1d91..5fec9c5 100644
--- a/message/message.go
+++ b/message/message.go
@@ -5,13 +5,14 @@
 // Package message implements formatted I/O for localized strings with functions
 // analogous to the fmt's print functions.
 //
-// Under construction. See https://golang.org/design/text/12750-localization
+// NOTE: Under construction. See https://golang.org/design/text/12750-localization
 // and its corresponding proposal issue https://golang.org/issues/12750.
 package message // import "golang.org/x/text/message"
 
 import (
 	"fmt"
 	"io"
+	"strings"
 
 	"golang.org/x/text/internal/format"
 	"golang.org/x/text/language"
@@ -22,6 +23,8 @@
 type Printer struct {
 	tag language.Tag
 
+	cat *Catalog
+
 	// NOTE: limiting one goroutine per Printer allows for many optimizations
 	// and simplifications. We can consider removing this restriction down the
 	// road if it the benefits do not seem to outweigh the disadvantages.
@@ -29,7 +32,7 @@
 
 // NewPrinter returns a Printer that formats messages tailored to language t.
 func NewPrinter(t language.Tag) *Printer {
-	return &Printer{tag: t}
+	return DefaultCatalog.Printer(t)
 }
 
 // Sprint is like fmt.Sprint, but using language-specific formatting.
@@ -47,6 +50,97 @@
 	return fmt.Print(p.bindArgs(a)...)
 }
 
+// Sprintln is like fmt.Sprintln, but using language-specific formatting.
+func (p *Printer) Sprintln(a ...interface{}) string {
+	return fmt.Sprintln(p.bindArgs(a)...)
+}
+
+// Fprintln is like fmt.Fprintln, but using language-specific formatting.
+func (p *Printer) Fprintln(w io.Writer, a ...interface{}) (n int, err error) {
+	return fmt.Fprintln(w, p.bindArgs(a)...)
+}
+
+// Println is like fmt.Println, but using language-specific formatting.
+func (p *Printer) Println(a ...interface{}) (n int, err error) {
+	return fmt.Println(p.bindArgs(a)...)
+}
+
+// Sprintf is like fmt.Sprintf, but using language-specific formatting.
+func (p *Printer) Sprintf(key Reference, a ...interface{}) string {
+	msg, hasSub := p.lookup(key)
+	if !hasSub {
+		return fmt.Sprintf(msg) // work around limitation of fmt
+	}
+	return fmt.Sprintf(msg, p.bindArgs(a)...)
+}
+
+// Fprintf is like fmt.Fprintf, but using language-specific formatting.
+func (p *Printer) Fprintf(w io.Writer, key Reference, a ...interface{}) (n int, err error) {
+	msg, hasSub := p.lookup(key)
+	if !hasSub {
+		return fmt.Fprintf(w, msg) // work around limitation of fmt
+	}
+	return fmt.Fprintf(w, msg, p.bindArgs(a)...)
+}
+
+// Printf is like fmt.Printf, but using language-specific formatting.
+func (p *Printer) Printf(key Reference, a ...interface{}) (n int, err error) {
+	msg, hasSub := p.lookup(key)
+	if !hasSub {
+		return fmt.Printf(msg) // work around limitation of fmt
+	}
+	return fmt.Printf(msg, p.bindArgs(a)...)
+}
+
+func (p *Printer) lookup(r Reference) (msg string, hasSub bool) {
+	var id string
+	switch v := r.(type) {
+	case string:
+		id, msg = v, v
+	case key:
+		id, msg = v.id, v.fallback
+	default:
+		panic("key argument is not a Reference")
+	}
+	if s, ok := p.cat.get(p.tag, id); ok {
+		msg = s
+	}
+	// fmt does not allow all arguments to be dropped in a format string. It
+	// only allows arguments to be dropped if at least one of the substitutions
+	// uses the positional marker (e.g. %[1]s). This hack works around this.
+	// TODO: This is only an approximation of the parsing of substitution
+	// patterns. Make more precise once we know if we can get by with fmt's
+	// formatting, which may not be the case.
+	for i := 0; i < len(msg)-1; i++ {
+		if msg[i] == '%' {
+			for i++; i < len(msg); i++ {
+				if strings.IndexByte("[]#+- *01234567890.", msg[i]) < 0 {
+					break
+				}
+			}
+			if i < len(msg) && msg[i] != '%' {
+				hasSub = true
+				break
+			}
+		}
+	}
+	return msg, hasSub
+}
+
+// A Reference is a string or a message reference.
+type Reference interface {
+}
+
+// Key creates a message Reference for a message where the given id is used for
+// message lookup and the fallback is returned when no matches are found.
+func Key(id string, fallback string) Reference {
+	return key{id, fallback}
+}
+
+type key struct {
+	id, fallback string
+}
+
 // bindArgs wraps arguments with implementation of fmt.Formatter, if needed.
 func (p *Printer) bindArgs(a []interface{}) []interface{} {
 	out := make([]interface{}, len(a))
diff --git a/message/message_test.go b/message/message_test.go
index 2c47701..f7dba8d 100644
--- a/message/message_test.go
+++ b/message/message_test.go
@@ -47,3 +47,103 @@
 		}
 	}
 }
+
+func TestFormatSelection(t *testing.T) {
+	type test struct {
+		tag  string
+		key  Reference
+		args []interface{}
+		want string
+	}
+	empty := []interface{}{}
+	joe := []interface{}{"Joe"}
+	joeAndMary := []interface{}{"Joe", "Mary"}
+
+	testCases := []struct {
+		desc string
+		cat  []entry
+		test []test
+	}{{
+		desc: "empty",
+		test: []test{
+			{"en", "key", empty, "key"},
+			{"en", "", empty, ""},
+			{"nl", "", empty, ""},
+		},
+	}, {
+		desc: "hierarchical languages",
+		cat: []entry{
+			{"en", "hello %s", "Hello %s!"},
+			{"en-GB", "hello %s", "Hellø %s!"},
+			{"en-US", "hello %s", "Howdy %s!"},
+			{"en", "greetings %s and %s", "Greetings %s and %s!"},
+		},
+		test: []test{
+			{"und", "hello %s", joe, "hello Joe"},
+			{"nl", "hello %s", joe, "hello Joe"},
+			{"en", "hello %s", joe, "Hello Joe!"},
+			{"en-US", "hello %s", joe, "Howdy Joe!"},
+			{"en-GB", "hello %s", joe, "Hellø Joe!"},
+			{"en-oxendict", "hello %s", joe, "Hello Joe!"},
+			{"en-US-oxendict-u-ms-metric", "hello %s", joe, "Howdy Joe!"},
+
+			{"und", "greetings %s and %s", joeAndMary, "greetings Joe and Mary"},
+			{"nl", "greetings %s and %s", joeAndMary, "greetings Joe and Mary"},
+			{"en", "greetings %s and %s", joeAndMary, "Greetings Joe and Mary!"},
+			{"en-US", "greetings %s and %s", joeAndMary, "Greetings Joe and Mary!"},
+			{"en-GB", "greetings %s and %s", joeAndMary, "Greetings Joe and Mary!"},
+			{"en-oxendict", "greetings %s and %s", joeAndMary, "Greetings Joe and Mary!"},
+			{"en-US-oxendict-u-ms-metric", "greetings %s and %s", joeAndMary, "Greetings Joe and Mary!"},
+		},
+	}, {
+		desc: "references",
+		cat: []entry{
+			{"en", "hello", "Hello!"},
+		},
+		test: []test{
+			{"en", "hello", empty, "Hello!"},
+			{"en", Key("hello", "fallback"), empty, "Hello!"},
+			{"en", Key("xxx", "fallback"), empty, "fallback"},
+			{"und", Key("hello", "fallback"), empty, "fallback"},
+		},
+	}, {
+		desc: "zero substitution", // work around limitation of fmt
+		cat: []entry{
+			{"en", "hello %s", "Hello!"},
+			{"en", "hi %s and %s", "Hello %[2]s!"},
+		},
+		test: []test{
+			{"en", "hello %s", joe, "Hello!"},
+			{"en", "hello %s", joeAndMary, "Hello!"},
+			{"en", "hi %s and %s", joeAndMary, "Hello Mary!"},
+			// The following tests resolve to the fallback string.
+			{"und", "hello", joeAndMary, "hello"},
+			{"und", "hello %%%%", joeAndMary, "hello %%"},
+			{"und", "hello %#%%4.2%  ", joeAndMary, "hello %%  "},
+			{"und", "hello %s", joeAndMary, "hello Joe%!(EXTRA string=Mary)"},
+			{"und", "hello %+%%s", joeAndMary, "hello %Joe%!(EXTRA string=Mary)"},
+			{"und", "hello %-42%%s ", joeAndMary, "hello %Joe %!(EXTRA string=Mary)"},
+		},
+	}}
+
+	for _, tc := range testCases {
+		cat, _ := initCat(tc.cat)
+
+		for i, pt := range tc.test {
+			p := cat.Printer(language.MustParse(pt.tag))
+
+			if got := p.Sprintf(pt.key, pt.args...); got != pt.want {
+				t.Errorf("%s:%d:Sprintf(%s, %v) = %s; want %s",
+					tc.desc, i, pt.key, pt.args, got, pt.want)
+				continue // Next error will likely be the same.
+			}
+
+			w := &bytes.Buffer{}
+			p.Fprintf(w, pt.key, pt.args...)
+			if got := w.String(); got != pt.want {
+				t.Errorf("%s:%d:Fprintf(%s, %v) = %s; want %s",
+					tc.desc, i, pt.key, pt.args, got, pt.want)
+			}
+		}
+	}
+}