diff --git a/com.google.eclipse.protobuf.test/src/com/google/eclipse/protobuf/validation/ProtobufJavaValidator_checkMapTypeHasValidKeyType_Test.java b/com.google.eclipse.protobuf.test/src/com/google/eclipse/protobuf/validation/ProtobufJavaValidator_checkMapTypeHasValidKeyType_Test.java
new file mode 100644
index 0000000..ef57d47
--- /dev/null
+++ b/com.google.eclipse.protobuf.test/src/com/google/eclipse/protobuf/validation/ProtobufJavaValidator_checkMapTypeHasValidKeyType_Test.java
@@ -0,0 +1,148 @@
+/*
+ * Copyright (c) 2014 Google Inc.
+ *
+ * All rights reserved. This program and the accompanying materials are made available under the terms of the Eclipse
+ * Public License v1.0 which accompanies this distribution, and is available at
+ *
+ * http://www.eclipse.org/legal/epl-v10.html
+ */
+package com.google.eclipse.protobuf.validation;
+
+import static com.google.eclipse.protobuf.junit.core.UnitTestModule.unitTestModule;
+import static com.google.eclipse.protobuf.junit.core.XtextRule.overrideRuntimeModuleWith;
+import static com.google.eclipse.protobuf.protobuf.ProtobufPackage.Literals.MAP_TYPE__KEY_TYPE;
+import static com.google.eclipse.protobuf.validation.Messages.invalidMapKeyType;
+import static com.google.eclipse.protobuf.validation.ProtobufJavaValidator.INVALID_MAP_KEY_TYPE_ERROR;
+import static org.eclipse.xtext.validation.ValidationMessageAcceptor.INSIGNIFICANT_INDEX;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.verify;
+import static org.mockito.Mockito.verifyZeroInteractions;
+
+import com.google.eclipse.protobuf.junit.core.XtextRule;
+import com.google.eclipse.protobuf.protobuf.MapType;
+import com.google.eclipse.protobuf.protobuf.MapTypeLink;
+import com.google.eclipse.protobuf.protobuf.MessageField;
+import com.google.inject.Inject;
+
+import org.eclipse.xtext.validation.ValidationMessageAcceptor;
+import org.junit.Before;
+import org.junit.Rule;
+import org.junit.Test;
+
+/**
+ * Tests for <code>{@link ProtobufJavaValidator#checkMapTypeHasValidKeyType(MapType)}</code>
+ */
+public class ProtobufJavaValidator_checkMapTypeHasValidKeyType_Test {
+  @Rule public XtextRule xtext = overrideRuntimeModuleWith(unitTestModule());
+
+  @Inject private ProtobufJavaValidator validator;
+  private ValidationMessageAcceptor messageAcceptor;
+
+  @Before public void setUp() {
+    messageAcceptor = mock(ValidationMessageAcceptor.class);
+    validator.setMessageAcceptor(messageAcceptor);
+  }
+
+  // syntax = "proto2";
+  //
+  // message Bar {}
+  //
+  // message Foo {
+  //   map<Bar, string> bar = 1;
+  // }
+  @Test public void should_create_error_if_key_type_is_message() {
+    MessageField field = xtext.find("bar", MessageField.class);
+    MapType map = ((MapTypeLink) field.getType()).getTarget();
+    validator.checkMapTypeHasValidKeyType(map);
+    verify(messageAcceptor).acceptError(invalidMapKeyType, map, MAP_TYPE__KEY_TYPE,
+        INSIGNIFICANT_INDEX, INVALID_MAP_KEY_TYPE_ERROR);
+  }
+
+  // syntax = "proto2";
+  //
+  // message Foo {
+  //   map<double, string> bar = 1;
+  // }
+  @Test public void should_create_error_if_key_type_is_double() {
+    MessageField field = xtext.find("bar", MessageField.class);
+    MapType map = ((MapTypeLink) field.getType()).getTarget();
+    validator.checkMapTypeHasValidKeyType(map);
+    verify(messageAcceptor).acceptError(invalidMapKeyType, map, MAP_TYPE__KEY_TYPE,
+        INSIGNIFICANT_INDEX, INVALID_MAP_KEY_TYPE_ERROR);
+  }
+
+  // syntax = "proto2";
+  //
+  // message Foo {
+  //   map<float, string> bar = 1;
+  // }
+  @Test public void should_create_error_if_key_type_is_float() {
+    MessageField field = xtext.find("bar", MessageField.class);
+    MapType map = ((MapTypeLink) field.getType()).getTarget();
+    validator.checkMapTypeHasValidKeyType(map);
+    verify(messageAcceptor).acceptError(invalidMapKeyType, map, MAP_TYPE__KEY_TYPE,
+        INSIGNIFICANT_INDEX, INVALID_MAP_KEY_TYPE_ERROR);
+  }
+
+  // syntax = "proto2";
+  //
+  // message Foo {
+  //   map<bytes, string> bar = 1;
+  // }
+  @Test public void should_create_error_if_key_type_is_bytes() {
+    MessageField field = xtext.find("bar", MessageField.class);
+    MapType map = ((MapTypeLink) field.getType()).getTarget();
+    validator.checkMapTypeHasValidKeyType(map);
+    verify(messageAcceptor).acceptError(invalidMapKeyType, map, MAP_TYPE__KEY_TYPE,
+        INSIGNIFICANT_INDEX, INVALID_MAP_KEY_TYPE_ERROR);
+  }
+
+  // syntax = "proto2";
+  //
+  // message Foo {
+  //   map<map<string, string>, string> bar = 1;
+  // }
+  @Test public void should_create_error_if_key_type_is_map() {
+    MessageField field = xtext.find("bar", MessageField.class);
+    MapType map = ((MapTypeLink) field.getType()).getTarget();
+    validator.checkMapTypeHasValidKeyType(map);
+    verify(messageAcceptor).acceptError(invalidMapKeyType, map, MAP_TYPE__KEY_TYPE,
+        INSIGNIFICANT_INDEX, INVALID_MAP_KEY_TYPE_ERROR);
+  }
+
+  // syntax = "proto2";
+  //
+  // message Foo {
+  //   map<bool, string> bar = 1;
+  // }
+  @Test public void should_not_create_error_if_key_type_is_bool() {
+    MessageField field = xtext.find("bar", MessageField.class);
+    MapType map = ((MapTypeLink) field.getType()).getTarget();
+    validator.checkMapTypeHasValidKeyType(map);
+    verifyZeroInteractions(messageAcceptor);
+  }
+
+  // syntax = "proto2";
+  //
+  // message Foo {
+  //   map<int32, string> bar = 1;
+  // }
+  @Test public void should_not_create_error_if_key_type_is_scalar() {
+    MessageField field = xtext.find("bar", MessageField.class);
+    MapType map = ((MapTypeLink) field.getType()).getTarget();
+    validator.checkMapTypeHasValidKeyType(map);
+    verifyZeroInteractions(messageAcceptor);
+  }
+
+  // syntax = "proto2";
+  //
+  // message Foo {
+  //   map<string, string> bar = 1;
+  // }
+  @Test public void should_not_create_error_if_key_type_is_string() {
+    MessageField field = xtext.find("bar", MessageField.class);
+    MapType map = ((MapTypeLink) field.getType()).getTarget();
+    validator.checkMapTypeHasValidKeyType(map);
+    verifyZeroInteractions(messageAcceptor);
+  }
+}
diff --git a/com.google.eclipse.protobuf.test/src/com/google/eclipse/protobuf/validation/ProtobufJavaValidator_checkMapTypeHasValidValueType_Test.java b/com.google.eclipse.protobuf.test/src/com/google/eclipse/protobuf/validation/ProtobufJavaValidator_checkMapTypeHasValidValueType_Test.java
new file mode 100644
index 0000000..1893d66
--- /dev/null
+++ b/com.google.eclipse.protobuf.test/src/com/google/eclipse/protobuf/validation/ProtobufJavaValidator_checkMapTypeHasValidValueType_Test.java
@@ -0,0 +1,72 @@
+/*
+ * Copyright (c) 2014 Google Inc.
+ *
+ * All rights reserved. This program and the accompanying materials are made available under the terms of the Eclipse
+ * Public License v1.0 which accompanies this distribution, and is available at
+ *
+ * http://www.eclipse.org/legal/epl-v10.html
+ */
+package com.google.eclipse.protobuf.validation;
+
+import static com.google.eclipse.protobuf.junit.core.UnitTestModule.unitTestModule;
+import static com.google.eclipse.protobuf.junit.core.XtextRule.overrideRuntimeModuleWith;
+import static com.google.eclipse.protobuf.protobuf.ProtobufPackage.Literals.MAP_TYPE__VALUE_TYPE;
+import static com.google.eclipse.protobuf.validation.Messages.invalidMapValueType;
+import static com.google.eclipse.protobuf.validation.ProtobufJavaValidator.MAP_WITH_MAP_VALUE_TYPE_ERROR;
+import static org.eclipse.xtext.validation.ValidationMessageAcceptor.INSIGNIFICANT_INDEX;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.verify;
+import static org.mockito.Mockito.verifyZeroInteractions;
+
+import com.google.eclipse.protobuf.junit.core.XtextRule;
+import com.google.eclipse.protobuf.protobuf.MapType;
+import com.google.eclipse.protobuf.protobuf.MapTypeLink;
+import com.google.eclipse.protobuf.protobuf.MessageField;
+import com.google.inject.Inject;
+
+import org.eclipse.xtext.validation.ValidationMessageAcceptor;
+import org.junit.Before;
+import org.junit.Rule;
+import org.junit.Test;
+
+/**
+ * Tests for <code>{@link ProtobufJavaValidator#checkMapTypeHasValidValueType(MapType)}</code>
+ */
+public class ProtobufJavaValidator_checkMapTypeHasValidValueType_Test {
+  @Rule public XtextRule xtext = overrideRuntimeModuleWith(unitTestModule());
+
+  @Inject private ProtobufJavaValidator validator;
+  private ValidationMessageAcceptor messageAcceptor;
+
+  @Before public void setUp() {
+    messageAcceptor = mock(ValidationMessageAcceptor.class);
+    validator.setMessageAcceptor(messageAcceptor);
+  }
+
+  // syntax = "proto2";
+  //
+  // message Foo {
+  //   map<string, map<string, string> > bar = 1;
+  // }
+  @Test public void should_create_error_if_value_type_is_map() {
+    MessageField field = xtext.find("bar", MessageField.class);
+    MapType map = ((MapTypeLink) field.getType()).getTarget();
+    validator.checkMapTypeHasValidValueType(map);
+    verify(messageAcceptor).acceptError(invalidMapValueType, map, MAP_TYPE__VALUE_TYPE,
+        INSIGNIFICANT_INDEX, MAP_WITH_MAP_VALUE_TYPE_ERROR);
+  }
+
+  // syntax = "proto2";
+  //
+  // message Bar {}
+  //
+  // message Foo {
+  //   map<string, Bar> bar = 1;
+  // }
+  @Test public void should_not_create_error_if_value_type_is_message() {
+    MessageField field = xtext.find("bar", MessageField.class);
+    MapType map = ((MapTypeLink) field.getType()).getTarget();
+    validator.checkMapTypeHasValidValueType(map);
+    verifyZeroInteractions(messageAcceptor);
+  }
+}
diff --git a/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/Protobuf.xtext b/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/Protobuf.xtext
index fb0a8e6..6ef7ab7 100644
--- a/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/Protobuf.xtext
+++ b/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/Protobuf.xtext
@@ -107,7 +107,7 @@
   target=MapType;
 
 MapType:
-  ->'map' '<' fromType=TypeLink ',' toType=TypeLink '>';
+  ->'map' '<' keyType=TypeLink ',' valueType=TypeLink '>';
 
 Enum:
   ->'enum' name=Name '{'
diff --git a/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/model/util/MessageFields.java b/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/model/util/MessageFields.java
index 3c09143..e5d9f34 100644
--- a/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/model/util/MessageFields.java
+++ b/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/model/util/MessageFields.java
@@ -31,6 +31,7 @@
 import com.google.eclipse.protobuf.protobuf.Enum;
 import com.google.eclipse.protobuf.protobuf.Message;
 import com.google.eclipse.protobuf.protobuf.MessageField;
+import com.google.eclipse.protobuf.protobuf.ModifierEnum;
 import com.google.eclipse.protobuf.protobuf.ScalarType;
 import com.google.eclipse.protobuf.protobuf.ScalarTypeLink;
 import com.google.eclipse.protobuf.protobuf.TypeLink;
diff --git a/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/scoping/ProtobufScopeProvider.java b/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/scoping/ProtobufScopeProvider.java
index b71ed89..e9d8556 100644
--- a/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/scoping/ProtobufScopeProvider.java
+++ b/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/scoping/ProtobufScopeProvider.java
@@ -28,6 +28,8 @@
 import com.google.eclipse.protobuf.protobuf.GroupElement;
 import com.google.eclipse.protobuf.protobuf.IndexedElement;
 import com.google.eclipse.protobuf.protobuf.LiteralLink;
+import com.google.eclipse.protobuf.protobuf.MapType;
+import com.google.eclipse.protobuf.protobuf.MapTypeLink;
 import com.google.eclipse.protobuf.protobuf.Message;
 import com.google.eclipse.protobuf.protobuf.MessageField;
 import com.google.eclipse.protobuf.protobuf.MessageLink;
@@ -84,6 +86,12 @@
   @SuppressWarnings("unused")
   public IScope scope_ComplexTypeLink_target(ComplexTypeLink link, EReference r) {
     EObject c = link.eContainer();
+    if (c instanceof MapType) {
+      c = c.eContainer();
+    }
+    if (c instanceof MapTypeLink) {
+      c = c.eContainer();
+    }
     if (c instanceof MessageField) {
       MessageField field = (MessageField) c;
       Collection<IEObjectDescription> complexTypes = potentialComplexTypesFor(field);
diff --git a/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/validation/Messages.java b/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/validation/Messages.java
index 184ec86..8b6c645 100644
--- a/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/validation/Messages.java
+++ b/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/validation/Messages.java
@@ -27,6 +27,8 @@
   public static String fieldNumbersMustBePositive;
   public static String importingUnsupportedSyntax;
   public static String importNotFound;
+  public static String invalidMapKeyType;
+  public static String invalidMapValueType;
   public static String literalNotInEnum;
   public static String mapWithModifier;
   public static String missingFieldNumber;
diff --git a/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/validation/Messages.properties b/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/validation/Messages.properties
index 1c061db..df4f28f 100644
--- a/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/validation/Messages.properties
+++ b/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/validation/Messages.properties
@@ -11,6 +11,8 @@
 fieldNumbersMustBePositive = Field numbers must be positive integers.
 importingUnsupportedSyntax = Importing unsupported file (directly or indirectly.) This may cause errors related to unresolved references.
 importNotFound = Import \"%s\" was not found.
+invalidMapKeyType = Key in a map field cannot be of float, double, bytes or message type.
+invalidMapValueType = Value in a map field cannot be a map.
 literalNotInEnum = Enum type \"%s\" has no value named \"%s\".
 mapWithModifier = Field labels (required/optional/repeated) are not allowed on map fields.
 missingFieldNumber = Missing field number.
diff --git a/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/validation/ProtobufJavaValidator.java b/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/validation/ProtobufJavaValidator.java
index 3a83d80..adbb50d 100644
--- a/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/validation/ProtobufJavaValidator.java
+++ b/com.google.eclipse.protobuf/src/com/google/eclipse/protobuf/validation/ProtobufJavaValidator.java
@@ -8,6 +8,8 @@
  */
 package com.google.eclipse.protobuf.validation;
 
+import static com.google.eclipse.protobuf.protobuf.ProtobufPackage.Literals.MAP_TYPE__KEY_TYPE;
+import static com.google.eclipse.protobuf.protobuf.ProtobufPackage.Literals.MAP_TYPE__VALUE_TYPE;
 import static com.google.eclipse.protobuf.protobuf.ProtobufPackage.Literals.MESSAGE_FIELD__MODIFIER;
 import static com.google.eclipse.protobuf.protobuf.ProtobufPackage.Literals.PACKAGE__NAME;
 import static com.google.eclipse.protobuf.protobuf.ProtobufPackage.Literals.SYNTAX__NAME;
@@ -15,6 +17,8 @@
 import static com.google.eclipse.protobuf.validation.Messages.expectedSyntaxIdentifier;
 import static com.google.eclipse.protobuf.validation.Messages.fieldNumberAlreadyUsed;
 import static com.google.eclipse.protobuf.validation.Messages.fieldNumbersMustBePositive;
+import static com.google.eclipse.protobuf.validation.Messages.invalidMapKeyType;
+import static com.google.eclipse.protobuf.validation.Messages.invalidMapValueType;
 import static com.google.eclipse.protobuf.validation.Messages.mapWithModifier;
 import static com.google.eclipse.protobuf.validation.Messages.missingModifier;
 import static com.google.eclipse.protobuf.validation.Messages.multiplePackages;
@@ -28,6 +32,7 @@
 import com.google.eclipse.protobuf.model.util.Protobufs;
 import com.google.eclipse.protobuf.naming.NameResolver;
 import com.google.eclipse.protobuf.protobuf.IndexedElement;
+import com.google.eclipse.protobuf.protobuf.MapType;
 import com.google.eclipse.protobuf.protobuf.MapTypeLink;
 import com.google.eclipse.protobuf.protobuf.Message;
 import com.google.eclipse.protobuf.protobuf.MessageElement;
@@ -37,7 +42,10 @@
 import com.google.eclipse.protobuf.protobuf.Package;
 import com.google.eclipse.protobuf.protobuf.Protobuf;
 import com.google.eclipse.protobuf.protobuf.ProtobufElement;
+import com.google.eclipse.protobuf.protobuf.ScalarType;
+import com.google.eclipse.protobuf.protobuf.ScalarTypeLink;
 import com.google.eclipse.protobuf.protobuf.Syntax;
+import com.google.eclipse.protobuf.protobuf.TypeLink;
 import com.google.inject.Inject;
 
 import org.eclipse.emf.ecore.EObject;
@@ -57,6 +65,8 @@
   public static final String MISSING_MODIFIER_ERROR = "noModifier";
   public static final String MAP_WITH_MODIFIER_ERROR = "mapWithModifier";
   public static final String REQUIRED_IN_PROTO3_ERROR = "requiredInProto3";
+  public static final String INVALID_MAP_KEY_TYPE_ERROR = "invalidMapKeyType";
+  public static final String MAP_WITH_MAP_VALUE_TYPE_ERROR = "mapWithMapValueType";
 
   @Inject private IndexedElements indexedElements;
   @Inject private NameResolver nameResolver;
@@ -197,4 +207,25 @@
   private boolean isNameNull(IndexedElement e) {
     return nameResolver.nameOf(e) == null;
   }
+
+  @Check public void checkMapTypeHasValidKeyType(MapType map) {
+    TypeLink keyType = map.getKeyType();
+    if (!(keyType instanceof ScalarTypeLink)) {
+      error(invalidMapKeyType, map, MAP_TYPE__KEY_TYPE, INVALID_MAP_KEY_TYPE_ERROR);
+      return;
+    }
+    ScalarType scalarKeyType = ((ScalarTypeLink) keyType).getTarget();
+    if (scalarKeyType == ScalarType.BYTES || scalarKeyType == ScalarType.DOUBLE
+        || scalarKeyType == ScalarType.FLOAT) {
+      error(invalidMapKeyType, map, MAP_TYPE__KEY_TYPE, INVALID_MAP_KEY_TYPE_ERROR);
+    }
+  }
+
+  @Check public void checkMapTypeHasValidValueType(MapType map) {
+    TypeLink keyType = map.getValueType();
+    if (keyType instanceof MapTypeLink) {
+      error(invalidMapValueType, map, MAP_TYPE__VALUE_TYPE, MAP_WITH_MAP_VALUE_TYPE_ERROR);
+      return;
+    }
+  }
 }