diff --git a/syncbase/key.go b/syncbase/key.go
index 34353af..362631c 100644
--- a/syncbase/key.go
+++ b/syncbase/key.go
@@ -4,7 +4,83 @@
 
 package syncbase
 
+import (
+	"bytes"
+	"crypto/rand"
+	"encoding/base64"
+	"encoding/binary"
+	"fmt"
+	"sync/atomic"
+	"time"
+)
+
+const (
+	// First character of UUID to make the UUID start with a valid identifier character.
+	// Can be used for versioning.
+	uuidPrefix string = "v"
+	// Legal characters of Java identifiers in ASCII-encoding order.
+	uuidCharacterSet string = "$0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz"
+)
+
+var (
+	invocationCounter uint32
+	base64Encoding    *base64.Encoding
+)
+
+func init() {
+	base64Encoding = base64.NewEncoding(uuidCharacterSet).WithPadding(base64.NoPadding)
+}
+
+// Resize string 's' to 'length'. The string will be padded with the first character from the
+// uuidCharacterSet if it is too short, and cut off if its too long.
+func resize(s string, length int) string {
+	switch {
+	case len(s) > length:
+		return s[len(s)-length:]
+	case len(s) == length:
+		return s
+	default:
+		for len(s) < length {
+			return uuidCharacterSet[:1] + s
+		}
+		return s
+	}
+}
+
+// UUID generates a sequential and pseudo-random key that can be used as an ID within
+// Syncbase. The generates IDs are of the format [a-zA-z][a-zA-Z0-9$_]{19}
+//
+// A UUID is made up of four parts:
+// - a prefix which gurantees that the generated UUID is a valid variable name in most programming
+//   languages
+// - a time component which uses nanosecond precision
+// - a counter component which is used to gurantee ordering between calls
+// - a random component which achieves pseude-randomness
 func UUID() string {
-	// TODO(kash): Implement me.
-	return ""
+	buffer := new(bytes.Buffer)
+
+	// Encode the current time in nanos as an base64-charater string.
+	// The maximum encoded length is 11 characters: 2^63/64^11 < 1
+	currentTime := time.Now().UnixNano()
+	binary.Write(buffer, binary.BigEndian, currentTime)
+	uuidTime := base64Encoding.EncodeToString(buffer.Bytes())
+
+	// Increment the global count of invocations and encde as a 3-character base64 string.
+	// Note that overflows here are fine.
+	buffer.Reset()
+	currentInvocation := atomic.AddUint32(&invocationCounter, 1)
+	binary.Write(buffer, binary.BigEndian, currentInvocation)
+	uuidInvocation := base64Encoding.EncodeToString(buffer.Next(4)[1:])
+
+	// Encode 4 bytes of randomness as base64-string (maximum of 6 characters)
+	random := make([]byte, 4)
+	rand.Read(random)
+	uuidRandNumber := base64Encoding.EncodeToString(random)
+
+	return fmt.Sprintf(
+		"%s%s%s%s",
+		resize(uuidPrefix, 1),
+		resize(uuidTime, 11),
+		resize(uuidInvocation, 2),
+		resize(uuidRandNumber, 6))
 }
diff --git a/syncbase/key_test.go b/syncbase/key_test.go
new file mode 100644
index 0000000..3ec9a3a
--- /dev/null
+++ b/syncbase/key_test.go
@@ -0,0 +1,66 @@
+// Copyright 2016 The Vanadium 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 syncbase_test
+
+import (
+	"regexp"
+	"sort"
+	"testing"
+
+	"v.io/v23/syncbase"
+)
+
+const (
+	uuidLoopIncovations int = 100
+)
+
+func TestUUIDFormat(t *testing.T) {
+	uuid := syncbase.UUID()
+	regexp := regexp.MustCompile("^v[\\$0-9A-Za-z_]{19}$")
+	if !regexp.MatchString(uuid) {
+		t.Error("Incorrect UUID format")
+	}
+}
+
+func TestUUIDCollisions(t *testing.T) {
+	uuidChannel := make(chan string)
+
+	createUUID := func() {
+		uuidChannel <- syncbase.UUID()
+	}
+
+	for i := 0; i < uuidLoopIncovations; i++ {
+		go createUUID()
+	}
+
+	uuidMap := make(map[string]bool)
+
+	for i := 0; i < uuidLoopIncovations; i++ {
+		uuidMap[<-uuidChannel] = true
+	}
+
+	if len(uuidMap) != uuidLoopIncovations {
+		t.Errorf("UUID collision for %d UUIDs", uuidLoopIncovations-len(uuidMap))
+	}
+}
+
+func TestUUIDSequential(t *testing.T) {
+	unsorted := make([]string, 100)
+	sorted := make([]string, 100)
+
+	for i := 0; i < uuidLoopIncovations; i++ {
+		uuid := syncbase.UUID()
+		unsorted[i] = uuid
+		sorted[i] = uuid
+	}
+
+	sort.Strings(sorted)
+
+	for i := 0; i < uuidLoopIncovations; i++ {
+		if unsorted[i] != sorted[i] {
+			t.Errorf("UUID not sorted at position %d", i)
+		}
+	}
+}