diff --git a/.travis.yml b/.travis.yml
index 2daa6fb..f3790dc 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -54,6 +54,8 @@
 #
 # TODO: SIMD support on stable releases
 # NOTE: SIMD support is unreliable on nightly; we track the latest release
+# NOTE: Test for alloc feature in no_std is not included here because it depends
+#       on the alloc crate stabilized in Rust 1.36.
 matrix:
   include:
     - rust: 1.32.0
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 88fba02..a2ae496 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -11,6 +11,7 @@
 ## [Unreleased]
 - Fix `no_std` behaviour, appropriately enable c2-chacha's `std` feature (#844)
 - Add a `no_std` target to CI to continously evaluate `no_std` status (#844)
+- `alloc` feature in `no_std` is available since Rust 1.36 (#856)
 
 ## [0.7.0] - 2019-06-28
 
diff --git a/README.md b/README.md
index b9d43e9..5acbadb 100644
--- a/README.md
+++ b/README.md
@@ -84,7 +84,7 @@
 Rand is built with these features enabled by default:
 
 -   `std` enables functionality dependent on the `std` lib
--   `alloc` (implied by `std`) enables functionality requiring an allocator
+-   `alloc` (implied by `std`) enables functionality requiring an allocator (when using this feature in `no_std`, Rand requires Rustc version 1.36 or greater)
 -   `getrandom` (implied by `std`) is an optional dependency providing the code
     behind `rngs::OsRng`
 
diff --git a/rand_core/CHANGELOG.md b/rand_core/CHANGELOG.md
index c96d886..5d35b6a 100644
--- a/rand_core/CHANGELOG.md
+++ b/rand_core/CHANGELOG.md
@@ -4,6 +4,9 @@
 The format is based on [Keep a Changelog](http://keepachangelog.com/en/1.0.0/)
 and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html).
 
+## [Unreleased]
+- `alloc` feature in `no_std` is available since Rust 1.36 (#856)
+
 ## [0.5.1] - 2019-09-02
 ### Added
 - `OsRng` added to `rand_core` (#863)