diff --git a/src/librustc_metadata/common.rs b/src/librustc_metadata/common.rs
index 2b972af..b3ca399 100644
--- a/src/librustc_metadata/common.rs
+++ b/src/librustc_metadata/common.rs
@@ -252,3 +252,7 @@
 }
 
 pub const tag_panic_strategy: usize = 0x114;
+
+// NB: increment this if you change the format of metadata such that
+// rustc_version can't be found.
+pub const metadata_encoding_version : &'static [u8] = &[b'r', b'u', b's', b't', 0, 0, 0, 2];
diff --git a/src/librustc_metadata/creader.rs b/src/librustc_metadata/creader.rs
index ad6bb2d..90f4ebc 100644
--- a/src/librustc_metadata/creader.rs
+++ b/src/librustc_metadata/creader.rs
@@ -12,7 +12,6 @@
 
 //! Validates all used crates and extern libraries and loads their metadata
 
-use common::rustc_version;
 use cstore::{self, CStore, CrateSource, MetadataBlob};
 use decoder;
 use loader::{self, CratePaths};
@@ -234,25 +233,6 @@
         return ret;
     }
 
-    fn verify_rustc_version(&self,
-                            name: &str,
-                            span: Span,
-                            metadata: &MetadataBlob) {
-        let crate_rustc_version = decoder::crate_rustc_version(metadata.as_slice());
-        if crate_rustc_version != Some(rustc_version()) {
-            let mut err = struct_span_fatal!(self.sess, span, E0514,
-                                             "the crate `{}` has been compiled with {}, which is \
-                                              incompatible with this version of rustc",
-                                              name,
-                                              crate_rustc_version
-                                              .as_ref().map(|s| &**s)
-                                              .unwrap_or("an old version of rustc"));
-            err.help("consider removing the compiled binaries and recompiling \
-                      with your current version of rustc");
-            err.emit();
-        }
-    }
-
     fn verify_no_symbol_conflicts(&self,
                                   span: Span,
                                   metadata: &MetadataBlob) {
@@ -294,7 +274,6 @@
                       explicitly_linked: bool)
                       -> (ast::CrateNum, Rc<cstore::crate_metadata>,
                           cstore::CrateSource) {
-        self.verify_rustc_version(name, span, &lib.metadata);
         self.verify_no_symbol_conflicts(span, &lib.metadata);
 
         // Claim this crate number and cache it
@@ -379,6 +358,7 @@
                     rejected_via_hash: vec!(),
                     rejected_via_triple: vec!(),
                     rejected_via_kind: vec!(),
+                    rejected_via_version: vec!(),
                     should_match_name: true,
                 };
                 match self.load(&mut load_ctxt) {
@@ -506,6 +486,7 @@
             rejected_via_hash: vec!(),
             rejected_via_triple: vec!(),
             rejected_via_kind: vec!(),
+            rejected_via_version: vec!(),
             should_match_name: true,
         };
         let library = self.load(&mut load_ctxt).or_else(|| {
diff --git a/src/librustc_metadata/csearch.rs b/src/librustc_metadata/csearch.rs
index b87b549..d1f6f7e 100644
--- a/src/librustc_metadata/csearch.rs
+++ b/src/librustc_metadata/csearch.rs
@@ -9,6 +9,7 @@
 // except according to those terms.
 
 use cstore;
+use common;
 use decoder;
 use encoder;
 use loader;
@@ -587,7 +588,7 @@
 
     fn metadata_encoding_version(&self) -> &[u8]
     {
-        encoder::metadata_encoding_version
+        common::metadata_encoding_version
     }
 
     /// Returns a map from a sufficiently visible external item (i.e. an external item that is
diff --git a/src/librustc_metadata/cstore.rs b/src/librustc_metadata/cstore.rs
index 2e1bdf2..5464f7e 100644
--- a/src/librustc_metadata/cstore.rs
+++ b/src/librustc_metadata/cstore.rs
@@ -15,6 +15,7 @@
 
 pub use self::MetadataBlob::*;
 
+use common;
 use creader;
 use decoder;
 use index;
@@ -311,20 +312,25 @@
 }
 
 impl MetadataBlob {
-    pub fn as_slice<'a>(&'a self) -> &'a [u8] {
-        let slice = match *self {
+    pub fn as_slice_raw<'a>(&'a self) -> &'a [u8] {
+        match *self {
             MetadataVec(ref vec) => &vec[..],
             MetadataArchive(ref ar) => ar.as_slice(),
-        };
-        if slice.len() < 4 {
+        }
+    }
+
+    pub fn as_slice<'a>(&'a self) -> &'a [u8] {
+        let slice = self.as_slice_raw();
+        let len_offset = 4 + common::metadata_encoding_version.len();
+        if slice.len() < len_offset+4 {
             &[] // corrupt metadata
         } else {
-            let len = (((slice[0] as u32) << 24) |
-                       ((slice[1] as u32) << 16) |
-                       ((slice[2] as u32) << 8) |
-                       ((slice[3] as u32) << 0)) as usize;
-            if len + 4 <= slice.len() {
-                &slice[4.. len + 4]
+            let len = (((slice[len_offset+0] as u32) << 24) |
+                       ((slice[len_offset+1] as u32) << 16) |
+                       ((slice[len_offset+2] as u32) << 8) |
+                       ((slice[len_offset+3] as u32) << 0)) as usize;
+            if len <= slice.len() - 4 - len_offset {
+                &slice[len_offset + 4..len_offset + len + 4]
             } else {
                 &[] // corrupt or old metadata
             }
diff --git a/src/librustc_metadata/encoder.rs b/src/librustc_metadata/encoder.rs
index 9286010..e862dbb 100644
--- a/src/librustc_metadata/encoder.rs
+++ b/src/librustc_metadata/encoder.rs
@@ -1851,10 +1851,6 @@
     }
 }
 
-// NB: Increment this as you change the metadata encoding version.
-#[allow(non_upper_case_globals)]
-pub const metadata_encoding_version : &'static [u8] = &[b'r', b'u', b's', b't', 0, 0, 0, 2 ];
-
 pub fn encode_metadata(ecx: EncodeContext, krate: &hir::Crate) -> Vec<u8> {
     let mut wr = Cursor::new(Vec::new());
 
@@ -1888,12 +1884,25 @@
     // the length of the metadata to the start of the metadata. Later on this
     // will allow us to slice the metadata to the precise length that we just
     // generated regardless of trailing bytes that end up in it.
-    let len = v.len() as u32;
-    v.insert(0, (len >>  0) as u8);
-    v.insert(0, (len >>  8) as u8);
-    v.insert(0, (len >> 16) as u8);
-    v.insert(0, (len >> 24) as u8);
-    return v;
+    //
+    // We also need to store the metadata encoding version here, because
+    // rlibs don't have it. To get older versions of rustc to ignore
+    // this metadata, there are 4 zero bytes at the start, which are
+    // treated as a length of 0 by old compilers.
+
+    let len = v.len();
+    let mut result = vec![];
+    result.push(0);
+    result.push(0);
+    result.push(0);
+    result.push(0);
+    result.extend(metadata_encoding_version.iter().cloned());
+    result.push((len >> 24) as u8);
+    result.push((len >> 16) as u8);
+    result.push((len >>  8) as u8);
+    result.push((len >>  0) as u8);
+    result.extend(v);
+    result
 }
 
 fn encode_metadata_inner(rbml_w: &mut Encoder,
diff --git a/src/librustc_metadata/loader.rs b/src/librustc_metadata/loader.rs
index a5b1c3d..dc10391 100644
--- a/src/librustc_metadata/loader.rs
+++ b/src/librustc_metadata/loader.rs
@@ -213,8 +213,8 @@
 //! metadata::loader or metadata::creader for all the juicy details!
 
 use cstore::{MetadataBlob, MetadataVec, MetadataArchive};
+use common::{metadata_encoding_version, rustc_version};
 use decoder;
-use encoder;
 
 use rustc::hir::svh::Svh;
 use rustc::session::Session;
@@ -260,6 +260,7 @@
     pub rejected_via_hash: Vec<CrateMismatch>,
     pub rejected_via_triple: Vec<CrateMismatch>,
     pub rejected_via_kind: Vec<CrateMismatch>,
+    pub rejected_via_version: Vec<CrateMismatch>,
     pub should_match_name: bool,
 }
 
@@ -336,6 +337,10 @@
             struct_span_err!(self.sess, self.span, E0462,
                              "found staticlib `{}` instead of rlib or dylib{}",
                              self.ident, add)
+        } else if !self.rejected_via_version.is_empty() {
+            struct_span_err!(self.sess, self.span, E0514,
+                             "found crate `{}` compiled by an incompatible version of rustc{}",
+                             self.ident, add)
         } else {
             struct_span_err!(self.sess, self.span, E0463,
                              "can't find crate for `{}`{}",
@@ -350,7 +355,7 @@
             }
         }
         if !self.rejected_via_hash.is_empty() {
-            err.note("perhaps this crate needs to be recompiled?");
+            err.note("perhaps that crate needs to be recompiled?");
             let mismatches = self.rejected_via_hash.iter();
             for (i, &CrateMismatch{ ref path, .. }) in mismatches.enumerate() {
                 err.note(&format!("crate `{}` path #{}: {}",
@@ -367,13 +372,22 @@
             }
         }
         if !self.rejected_via_kind.is_empty() {
-            err.help("please recompile this crate using --crate-type lib");
+            err.help("please recompile that crate using --crate-type lib");
             let mismatches = self.rejected_via_kind.iter();
             for (i, &CrateMismatch { ref path, .. }) in mismatches.enumerate() {
                 err.note(&format!("crate `{}` path #{}: {}",
                                   self.ident, i+1, path.display()));
             }
         }
+        if !self.rejected_via_version.is_empty() {
+            err.help(&format!("please recompile that crate using this compiler ({})",
+                              rustc_version()));
+            let mismatches = self.rejected_via_version.iter();
+            for (i, &CrateMismatch { ref path, ref got }) in mismatches.enumerate() {
+                err.note(&format!("crate `{}` path #{}: {} compiled by {:?}",
+                                  self.ident, i+1, path.display(), got));
+            }
+        }
 
         err.emit();
         self.sess.abort_if_errors();
@@ -591,6 +605,17 @@
     }
 
     fn crate_matches(&mut self, crate_data: &[u8], libpath: &Path) -> Option<Svh> {
+        let crate_rustc_version = decoder::crate_rustc_version(crate_data);
+        if crate_rustc_version != Some(rustc_version()) {
+            let message = crate_rustc_version.unwrap_or(format!("an unknown compiler"));
+            info!("Rejecting via version: expected {} got {}", rustc_version(), message);
+            self.rejected_via_version.push(CrateMismatch {
+                path: libpath.to_path_buf(),
+                got: message
+            });
+            return None;
+        }
+
         if self.should_match_name {
             match decoder::maybe_get_crate_name(crate_data) {
                 Some(ref name) if self.crate_name == *name => {}
@@ -742,6 +767,21 @@
     pub fn as_slice<'a>(&'a self) -> &'a [u8] { unsafe { &*self.data } }
 }
 
+fn verify_decompressed_encoding_version(blob: &MetadataBlob, filename: &Path)
+                                        -> Result<(), String>
+{
+    let data = blob.as_slice_raw();
+    if data.len() < 4+metadata_encoding_version.len() ||
+        !<[u8]>::eq(&data[..4], &[0, 0, 0, 0]) ||
+        &data[4..4+metadata_encoding_version.len()] != metadata_encoding_version
+    {
+        Err((format!("incompatible metadata version found: '{}'",
+                     filename.display())))
+    } else {
+        Ok(())
+    }
+}
+
 // Just a small wrapper to time how long reading metadata takes.
 fn get_metadata_section(target: &Target, flavor: CrateFlavor, filename: &Path)
                         -> Result<MetadataBlob, String> {
@@ -772,7 +812,10 @@
         return match ArchiveMetadata::new(archive).map(|ar| MetadataArchive(ar)) {
             None => Err(format!("failed to read rlib metadata: '{}'",
                                 filename.display())),
-            Some(blob) => Ok(blob)
+            Some(blob) => {
+                try!(verify_decompressed_encoding_version(&blob, filename));
+                Ok(blob)
+            }
         };
     }
     unsafe {
@@ -801,12 +844,12 @@
                 let cbuf = llvm::LLVMGetSectionContents(si.llsi);
                 let csz = llvm::LLVMGetSectionSize(si.llsi) as usize;
                 let cvbuf: *const u8 = cbuf as *const u8;
-                let vlen = encoder::metadata_encoding_version.len();
+                let vlen = metadata_encoding_version.len();
                 debug!("checking {} bytes of metadata-version stamp",
                        vlen);
                 let minsz = cmp::min(vlen, csz);
                 let buf0 = slice::from_raw_parts(cvbuf, minsz);
-                let version_ok = buf0 == encoder::metadata_encoding_version;
+                let version_ok = buf0 == metadata_encoding_version;
                 if !version_ok {
                     return Err((format!("incompatible metadata version found: '{}'",
                                         filename.display())));
@@ -817,7 +860,11 @@
                        csz - vlen);
                 let bytes = slice::from_raw_parts(cvbuf1, csz - vlen);
                 match flate::inflate_bytes(bytes) {
-                    Ok(inflated) => return Ok(MetadataVec(inflated)),
+                    Ok(inflated) => {
+                        let blob = MetadataVec(inflated);
+                        try!(verify_decompressed_encoding_version(&blob, filename));
+                        return Ok(blob);
+                    }
                     Err(_) => {}
                 }
             }
diff --git a/src/test/compile-fail/changing-crates.rs b/src/test/compile-fail/changing-crates.rs
index 0b42015..f74855a 100644
--- a/src/test/compile-fail/changing-crates.rs
+++ b/src/test/compile-fail/changing-crates.rs
@@ -17,7 +17,7 @@
 
 extern crate a;
 extern crate b; //~ ERROR: found possibly newer version of crate `a` which `b` depends on
-//~| NOTE: perhaps this crate needs to be recompiled
+//~| NOTE: perhaps that crate needs to be recompiled
 //~| NOTE: crate `a` path #1:
 //~| NOTE: crate `b` path #1:
 
diff --git a/src/test/compile-fail/svh-change-lit.rs b/src/test/compile-fail/svh-change-lit.rs
index eb92bcf..1638caa 100644
--- a/src/test/compile-fail/svh-change-lit.rs
+++ b/src/test/compile-fail/svh-change-lit.rs
@@ -17,7 +17,7 @@
 
 extern crate a;
 extern crate b; //~ ERROR: found possibly newer version of crate `a` which `b` depends on
-//~| NOTE: perhaps this crate needs to be recompiled
+//~| NOTE: perhaps that crate needs to be recompiled
 //~| NOTE: crate `a` path #1:
 //~| NOTE: crate `b` path #1:
 
diff --git a/src/test/compile-fail/svh-change-significant-cfg.rs b/src/test/compile-fail/svh-change-significant-cfg.rs
index 7c9e0d3..99523ca 100644
--- a/src/test/compile-fail/svh-change-significant-cfg.rs
+++ b/src/test/compile-fail/svh-change-significant-cfg.rs
@@ -17,7 +17,7 @@
 
 extern crate a;
 extern crate b; //~ ERROR: found possibly newer version of crate `a` which `b` depends on
-//~| NOTE: perhaps this crate needs to be recompiled
+//~| NOTE: perhaps that crate needs to be recompiled
 //~| NOTE: crate `a` path #1:
 //~| NOTE: crate `b` path #1:
 
diff --git a/src/test/compile-fail/svh-change-trait-bound.rs b/src/test/compile-fail/svh-change-trait-bound.rs
index 1e6a723..dcf4859 100644
--- a/src/test/compile-fail/svh-change-trait-bound.rs
+++ b/src/test/compile-fail/svh-change-trait-bound.rs
@@ -17,7 +17,7 @@
 
 extern crate a;
 extern crate b; //~ ERROR: found possibly newer version of crate `a` which `b` depends on
-//~| NOTE: perhaps this crate needs to be recompiled
+//~| NOTE: perhaps that crate needs to be recompiled
 //~| NOTE: crate `a` path #1:
 //~| NOTE: crate `b` path #1:
 
diff --git a/src/test/compile-fail/svh-change-type-arg.rs b/src/test/compile-fail/svh-change-type-arg.rs
index 73c35ee..7e51ca4 100644
--- a/src/test/compile-fail/svh-change-type-arg.rs
+++ b/src/test/compile-fail/svh-change-type-arg.rs
@@ -17,7 +17,7 @@
 
 extern crate a;
 extern crate b; //~ ERROR: found possibly newer version of crate `a` which `b` depends on
-//~| NOTE: perhaps this crate needs to be recompiled
+//~| NOTE: perhaps that crate needs to be recompiled
 //~| NOTE: crate `a` path #1:
 //~| NOTE: crate `b` path #1:
 
diff --git a/src/test/compile-fail/svh-change-type-ret.rs b/src/test/compile-fail/svh-change-type-ret.rs
index b8908e2..54ca87d 100644
--- a/src/test/compile-fail/svh-change-type-ret.rs
+++ b/src/test/compile-fail/svh-change-type-ret.rs
@@ -17,7 +17,7 @@
 
 extern crate a;
 extern crate b; //~ ERROR: found possibly newer version of crate `a` which `b` depends on
-//~| NOTE: perhaps this crate needs to be recompiled
+//~| NOTE: perhaps that crate needs to be recompiled
 //~| NOTE: crate `a` path #1:
 //~| NOTE: crate `b` path #1:
 
diff --git a/src/test/compile-fail/svh-change-type-static.rs b/src/test/compile-fail/svh-change-type-static.rs
index 291e441..ea90faa 100644
--- a/src/test/compile-fail/svh-change-type-static.rs
+++ b/src/test/compile-fail/svh-change-type-static.rs
@@ -17,7 +17,7 @@
 
 extern crate a;
 extern crate b; //~ ERROR: found possibly newer version of crate `a` which `b` depends on
-//~| NOTE: perhaps this crate needs to be recompiled
+//~| NOTE: perhaps that crate needs to be recompiled
 //~| NOTE: crate `a` path #1:
 //~| NOTE: crate `b` path #1:
 
diff --git a/src/test/compile-fail/svh-use-trait.rs b/src/test/compile-fail/svh-use-trait.rs
index ed816a9..c0a5a0a 100644
--- a/src/test/compile-fail/svh-use-trait.rs
+++ b/src/test/compile-fail/svh-use-trait.rs
@@ -22,7 +22,7 @@
 
 extern crate uta;
 extern crate utb; //~ ERROR: found possibly newer version of crate `uta` which `utb` depends
-//~| NOTE: perhaps this crate needs to be recompiled?
+//~| NOTE: perhaps that crate needs to be recompiled?
 //~| NOTE: crate `uta` path #1:
 //~| NOTE: crate `utb` path #1:
 
diff --git a/src/test/run-make/many-crates-but-no-match/Makefile b/src/test/run-make/many-crates-but-no-match/Makefile
index edf8e9d..0da4af3 100644
--- a/src/test/run-make/many-crates-but-no-match/Makefile
+++ b/src/test/run-make/many-crates-but-no-match/Makefile
@@ -28,7 +28,7 @@
 	# Ensure crateC fails to compile since A1 is "missing" and A2/A3 hashes do not match
 	$(RUSTC) -L $(A2) -L $(A3) crateC.rs >$(LOG) 2>&1 || true
 	grep "error: found possibly newer version of crate \`crateA\` which \`crateB\` depends on" $(LOG)
-	grep "note: perhaps this crate needs to be recompiled?" $(LOG)
+	grep "note: perhaps that crate needs to be recompiled?" $(LOG)
 	grep "note: crate \`crateA\` path #1:" $(LOG)
 	grep "note: crate \`crateA\` path #2:" $(LOG)
 	grep "note: crate \`crateB\` path #1:" $(LOG)