@@ -1665,6 +1665,13 @@ def axis_date(self, tz=None):
             tz = pytz.timezone(tz)
         self.update_units(datetime.datetime(2009, 1, 1, 0, 0, 0, 0, tz))
 
+    def get_tick_space(self):
+        """
+        Return the estimated number of ticks that can fit on the axis.
+        """
+        # Must be overridden in the subclass
+        raise NotImplementedError()
+
 
 class XAxis(Axis):
     __name__ = 'xaxis'
@@ -1988,6 +1995,17 @@ def set_default_intervals(self):
                 self.axes.viewLim.intervalx = xmin, xmax
         self.stale = True
 
+    def get_tick_space(self):
+        # TODO: cache this computation
+        ends = self.axes.transAxes.transform([[0, 0], [1, 0]])
+        length = ((ends[1][0] - ends[0][0]) / self.axes.figure.dpi) * 72.0
+        tick = self._get_tick(True)
+        # There is a heuristic here that the aspect ratio of tick text
+        # is no more than 4:1
+        size = tick.label1.get_size() * 4
+        size *= np.cos(np.deg2rad(tick.label1.get_rotation()))
+        return np.floor(length / size)
+
 
 class YAxis(Axis):
     __name__ = 'yaxis'
@@ -2318,3 +2336,13 @@ def set_default_intervals(self):
             if not viewMutated:
                 self.axes.viewLim.intervaly = ymin, ymax
         self.stale = True
+
+    def get_tick_space(self):
+        # TODO: cache this computation
+        ends = self.axes.transAxes.transform([[0, 0], [0, 1]])
+        length = ((ends[1][1] - ends[0][1]) / self.axes.figure.dpi) * 72.0
+        tick = self._get_tick(True)
+        # Having a spacing of at least 2 just looks good.
+        size = tick.label1.get_size() * 2.0
+        size *= np.cos(np.deg2rad(tick.label1.get_rotation()))
+        return np.floor(length / size)
@@ -1449,6 +1449,48 @@ def view_limits(self, dmin, dmax):
         return np.take(self.bin_boundaries(dmin, dmax), [0, -1])
 
 
+class AutoSpacedLocator(MaxNLocator):
+    """
+    Behaves like a MaxNLocator, except N is automatically determined
+    from the length of the axis.
+    """
+    def __init__(self, *args, **kwargs):
+        """
+        Keyword args:
+
+        *steps*
+            Sequence of nice numbers starting with 1 and ending with 10;
+            e.g., [1, 2, 4, 5, 10]
+
+        *integer*
+            If True, ticks will take only integer values.
+
+        *symmetric*
+            If True, autoscaling will result in a range symmetric
+            about zero.
+
+        *prune*
+            ['lower' | 'upper' | 'both' | None]
+            Remove edge ticks -- useful for stacked or ganged plots
+            where the upper tick of one axes overlaps with the lower
+            tick of the axes above it.
+            If prune=='lower', the smallest tick will
+            be removed.  If prune=='upper', the largest tick will be
+            removed.  If prune=='both', the largest and smallest ticks
+            will be removed.  If prune==None, no ticks will be removed.
+
+        """
+        if 'nbins' in kwargs:
+            raise ValueError(
+                'AutoSpacedLocator does not take nbins as an argument')
+        self.set_params(**self.default_params)
+        self.set_params(**kwargs)
+
+    def __call__(self):
+        self._nbins = self.axis.get_tick_space()
+        return super(AutoSpacedLocator, self).__call__()
+
+
 def decade_down(x, base=10):
     'floor x to the nearest lower decade'
     if x == 0.0:
@@ -1872,9 +1914,9 @@ def tick_values(self, vmin, vmax):
         return self.raise_if_exceeds(np.array(ticklocs))
 
 
-class AutoLocator(MaxNLocator):
+class AutoLocator(AutoSpacedLocator):
     def __init__(self):
-        MaxNLocator.__init__(self, nbins=9, steps=[1, 2, 5, 10])
+        AutoSpacedLocator.__init__(self, steps=[1, 2, 5, 10])
 
 
 class AutoMinorLocator(Locator):