diff --git a/doc/users/whats_new/plot_downsample.rst b/doc/users/whats_new/plot_downsample.rst
@@ -0,0 +1,7 @@
+Downsample line plots
+---------------------
+
+A ``downsample`` parameter now exists for the method :func:`plot`.  This
+allows line plots to be intelligently downsampled so that rendering and
+interaction is faster. The downsampling algorithm will render an image
+very similar to a non-downsampled image.
diff --git a/examples/pyplots/pyplot_downsample.py b/examples/pyplots/pyplot_downsample.py
@@ -0,0 +1,30 @@
+"""
+Demo of downsampling line plots.
+
+This method of downsampling will greatly speed up interaction
+and rendering time, without changing the actual rasterization too much.
+Try interacting with the two figures (panning, zooming, etc.) to see
+the difference.
+
+"""
+import numpy as np
+import matplotlib.pyplot as plt
+
+# Fixing random state for reproducibility
+np.random.seed(8675309)
+
+# make up some data
+y = np.random.normal(loc=0.5, scale=0.4, size=1000000)
+x = np.arange(len(y))
+
+# plot without downsampling
+plt.figure(1)
+plt.plot(x, y)
+
+# plot with downsampling
+plt.figure(2)
+plt.plot(x, y, downsample=True)
+
+plt.show()
+
+# interact with both figures to compare snapiness
diff --git a/lib/matplotlib/lines.py b/lib/matplotlib/lines.py
@@ -310,6 +310,7 @@ def __init__(self, xdata, ydata,
                  pickradius=5,
                  drawstyle=None,
                  markevery=None,
+                 downsample=None,
                  **kwargs
                  ):
         """
@@ -408,6 +409,8 @@ def __init__(self, xdata, ydata,
         self.set_antialiased(antialiased)
         self.set_markersize(markersize)
 
+        self._downsample = downsample
+
         self._markeredgecolor = None
         self._markeredgewidth = None
         self._markerfacecolor = None
@@ -583,6 +586,10 @@ def set_markevery(self, every):
         markers is always determined from the display-coordinates
         axes-bounding-box-diagonal regardless of the actual axes data limits.
 
+        See also
+        --------
+        downsample : for downsampling the line segments that are plotted.
+
         """
         if self._markevery != every:
             self.stale = True
@@ -592,6 +599,59 @@ def get_markevery(self):
         """return the markevery setting"""
         return self._markevery
 
+    @property
+    def downsample(self):
+        """Set the downsample property to subsample the plotted line segments.
+
+        If True, then only a subset of line segments will be plotted. The
+        subset is carefully chosen so that the rendering of the downsampled
+        plot looks very similar to the rending of the non-downsampled plot. In
+        fact, if there is no anti-aliasing and plotting uses a solid line only,
+        then the renderings will be identical.
+
+        Recommended *only* when plotting with a solid line (e.g. no dashes,
+        no markers).
+
+        Parameters
+        ----------
+        downsample : True | False
+            Whether or not to downsample.
+
+            - downsample=True, a downsampled set of points will be plotted.
+            - downsample=False, every point will be plotted.
+
+        Notes
+        -----
+        If the x-values of the line are monotonic, then the downsampling
+        algorithm will plot at most 4 times the width of the parent
+        :class:`matplotlib.axes.Axes` in pixels of vertices. If the x-values
+        are not monotonic, the plot will still render correctly, but you are
+        not guaranteed any faster rendering.
+
+        If plotting with a non-solid line format (e.g. '--'), then
+        the downsampled plot could render quite differently from the
+        non-downsampled plot.
+
+        Markers will not be downsampled.
+
+        If the line is anti-aliased, then the downsampled plot will not
+        render *exactly* the same as a non-dowsampled plot,
+        but will be very similar.
+
+        See also
+        --------
+        markevery : for downsampling the markers that are plotted.
+
+        """
+        return self._downsample
+
+    @downsample.setter
+    def downsample(self, downsample):
+        """Sets the downsample property."""
+        if self._downsample != downsample:
+            self.stale = True
+        self._downsample = downsample
+
     def set_picker(self, p):
         """Sets the event picker details for the line.
 
@@ -747,6 +807,57 @@ def _is_sorted(self, x):
         # We don't handle the monotonically decreasing case.
         return _path.is_sorted(x)
 
+    def _downsample_path(self, tpath, affine):
+        """
+        Helper function to compute the downsampled path.
+        """
+        # pull out the two bits of data we want from the path
+        codes, verts = tpath.codes, tpath.vertices
+
+        def _slice_or_none(in_v, slc):
+            """
+            Helper function to cope with `codes` being an ndarray or `None`
+            """
+            if in_v is None:
+                return None
+            return in_v[slc]
+
+        # Convert vertices from data space to pixel space.
+        # Any non-affine axis transformation has already been applied
+        # to tpath, so we just need to apply affine part.
+        verts_trans = affine.transform_path(tpath).vertices
+
+        # Find where the pixel column of the x data changes
+        split_indices = np.diff(np.floor(verts_trans[:, 0]).astype(int)) != 0
+        split_indices = np.where(split_indices)[0] + 1
+
+        # Don't waste time downsampling if it won't give us any benefit
+        # 4.0 was chosen somewhat arbitrarily.
+        if split_indices.size >= verts_trans.shape[0] / 4.0:
+            return tpath
+
+        keep_inds = np.zeros((split_indices.size + 1, 4), dtype=int)
+        for i, y_pixel_col in enumerate(np.split(verts_trans[:, 1],
+                                                 split_indices)):
+            try:
+                keep_inds[i, 1:3] = (np.nanargmin(y_pixel_col),
+                                     np.nanargmax(y_pixel_col))
+            except ValueError:
+                # np.nanarg* raises a ValueError if all elements are NaN.
+                # If either np.nanargmin or np.nanargmax raise this error,
+                # then all y_pixel_col is NaN. In this case, the argmin
+                # and argmax are both undefined, just keep the first value.
+                keep_inds[i, 1:3] = 0
+
+        starts = np.hstack((0, split_indices))
+        ends = np.hstack((split_indices, verts_trans.shape[0]))
+        keep_inds[:, :3] += starts[:, np.newaxis]
+        keep_inds[:, 3] = ends - 1
+
+        keep_inds = keep_inds.flatten()
+
+        return Path(verts[keep_inds], _slice_or_none(codes, keep_inds))
+
     @allow_rasterization
     def draw(self, renderer):
         """draw the Line with `renderer` unless visibility is False"""
@@ -775,6 +886,8 @@ def draw(self, renderer):
         if funcname != '_draw_nothing':
             tpath, affine = transf_path.get_transformed_path_and_affine()
             if len(tpath.vertices):
+                if self._downsample:
+                    tpath = self._downsample_path(tpath, affine)
                 line_func = getattr(self, funcname)
                 gc = renderer.new_gc()
                 self._set_gc_clip(gc)

diff --git a/lib/matplotlib/tests/test_lines.py b/lib/matplotlib/tests/test_lines.py
@@ -191,5 +191,55 @@ def test_nan_is_sorted():
     assert_true(not line._is_sorted([3, 5] + [np.nan] * 100 + [0, 2]))
 
 
+@cleanup
+def test_downsample_lines():
+    x = np.hstack((np.zeros(99), np.ones(99)))
+    y = np.hstack([2.0, 8.0, 3 * np.ones(95), 1.0, 5.0,
+                   5.0, 5.5, 6 * np.ones(95), 8.0, 7.0])
+
+    line = mlines.Line2D(x, y, downsample=True)
+
+    _, ax = plt.subplots()
+
+    ax.add_line(line)
+
+    transf_path = line._get_transformed_path()
+    tpath, affine = transf_path.get_transformed_path_and_affine()
+    down_verts = line._downsample_path(tpath, affine).vertices
+
+    expected_down_verts = np.array([
+        [0.0, 2.0],
+        [0.0, 1.0],
+        [0.0, 8.0],
+        [0.0, 5.0],
+        [1.0, 5.0],
+        [1.0, 5.0],
+        [1.0, 8.0],
+        [1.0, 7.0]
+    ])
+    assert_true(np.all(down_verts == expected_down_verts))
+
+
+@cleanup
+def test_downsample_nan_lines():
+    # Creates x and y data, add some NaN values
+    N = 10**5
+    x = np.linspace(0,1,N)
+    y = np.random.normal(size=N)
+    x[10000:30000] = np.nan
+    y[20000:40000] = np.nan
+
+    line = mlines.Line2D(x, y, downsample=True)
+
+    fig, ax = plt.subplots()
+
+    ax.add_line(line)
+
+    fig.canvas.draw()
+
+    # Nothing to assert here, we are just making sure NaN values
+    # do not raise any errors.
+
+
 if __name__ == '__main__':
     nose.runmodule(argv=['-s', '--with-doctest'], exit=False)