diff --git a/conman/interface.py b/conman/interface.py
index 50fe7a3..53fe0eb 100755
--- a/conman/interface.py
+++ b/conman/interface.py
@@ -154,33 +154,38 @@
     # If the current routes are the same, there is nothing to do.  If either
     # exists but is different, delete it before adding an updated one.
     current = self.current_routes()
-    default = current.get('default', {})
-    if ((default.get('via', None), default.get('metric', None)) !=
-        (self._gateway_ip, str(self.metric))):
-      logging.debug('Adding default route for dev %s', self.name)
-      self.delete_route('default')
-      self._ip_route('add', 'default',
-                     'via', self._gateway_ip,
-                     'dev', self.name,
-                     'metric', str(self.metric))
+
+    to_add = []
 
     subnet = current.get('subnet', {})
     if (self._subnet and
         (subnet.get('route', None), subnet.get('metric', None)) !=
         (self._subnet, str(self.metric))):
       logging.debug('Adding subnet route for dev %s', self.name)
-      self.delete_route('subnet')
-      self._ip_route('add', self._subnet,
-                     'dev', self.name,
-                     'metric', str(self.metric))
+      to_add.append(('subnet', ('add', self._subnet, 'dev', self.name,
+                                'metric', str(self.metric))))
+      subnet = self._subnet
+
+    default = current.get('default', {})
+    if (subnet and
+        (default.get('via', None), default.get('metric', None)) !=
+        (self._gateway_ip, str(self.metric))):
+      logging.debug('Adding default route for dev %s', self.name)
+      to_add.append(('default', ('add', 'default', 'via', self._gateway_ip,
+                                 'dev', self.name, 'metric', str(self.metric))))
 
     # RFC2365 multicast route.
     if current.get('multicast', {}).get('metric', None) != str(self.metric):
       logging.debug('Adding multicast route for dev %s', self.name)
-      self.delete_route('multicast')
-      self._ip_route('add', RFC2385_MULTICAST_ROUTE,
-                     'dev', self.name,
-                     'metric', str(self.metric))
+      to_add.append(('multicast', ('add', RFC2385_MULTICAST_ROUTE,
+                                   'dev', self.name,
+                                   'metric', str(self.metric))))
+
+    for route_type, _ in to_add[::-1]:
+      self.delete_route(route_type)
+
+    for _, cmd in to_add:
+      self._ip_route(*cmd)
 
   def delete_route(self, *args):
     """Delete default and/or subnet routes for this interface.
@@ -198,7 +203,8 @@
       raise ValueError(
           'Must specify at least one of default, subnet, multicast to delete.')
 
-    for route_type in args:
+    # Use a sorted list to ensure that default comes before subnet.
+    for route_type in sorted(list(args)):
       while route_type in self.current_routes():
         logging.debug('Deleting %s route for dev %s', route_type, self.name)
         self._ip_route('del', self.current_routes()[route_type]['route'],
diff --git a/conman/interface_test.py b/conman/interface_test.py
index e8ab4ca..45714a8 100755
--- a/conman/interface_test.py
+++ b/conman/interface_test.py
@@ -5,6 +5,8 @@
 import logging
 import os
 import shutil
+import socket
+import struct
 import tempfile
 import time
 
@@ -46,6 +48,29 @@
       raise ValueError('Invalid fake connection_check script.')
 
   def _really_ip_route(self, *args):
+    def can_add_route():
+      def ip_to_int(ip):
+        return struct.unpack('!I', socket.inet_pton(socket.AF_INET, ip))[0]
+
+      if args[1] != 'default':
+        return True
+
+      via = ip_to_int(args[args.index('via') + 1])
+      for (ifc, route, _), _ in self.routing_table.iteritems():
+        if ifc != self.name:
+          continue
+
+        netmask = 0
+        if '/' in route:
+          route, netmask = route.split('/')
+          netmask = 32 - int(netmask)
+        route = ip_to_int(route)
+
+        if (route >> netmask) == (via >> netmask):
+          return True
+
+      return False
+
     if not args:
       return '\n'.join(self.routing_table.values() +
                        ['1.2.3.4/24 dev fake0 proto kernel scope link',
@@ -61,6 +86,9 @@
       route = args[1]
     key = (self.name, route, metric)
     if args[0] == 'add' and key not in self.routing_table:
+      if not can_add_route():
+        raise ValueError('Tried to add default route without subnet route: %r',
+                         self.routing_table)
       logging.debug('Adding route for %r', key)
       self.routing_table[key] = ' '.join(args[1:])
     elif args[0] == 'del':
@@ -94,8 +122,8 @@
   """Fake wpactrl.WPACtrl."""
 
   # pylint: disable=unused-argument
-  def __init__(self, socket):
-    self._socket = socket
+  def __init__(self, wpa_socket):
+    self._socket = wpa_socket
     self.events = []
     self.attached = False
     self.connected = False
@@ -344,8 +372,8 @@
 
     b.add_moca_station(0)
     wvtest.WVFAIL(os.path.exists(autoprov_filepath))
-    b.set_gateway_ip('192.168.1.1')
     b.set_subnet('192.168.1.0/24')
+    b.set_gateway_ip('192.168.1.1')
     wvtest.WVFAIL(os.path.exists(autoprov_filepath))
     # Everything should fail because the interface is not initialized.
     wvtest.WVFAIL(b.acs())
@@ -403,6 +431,9 @@
     b.ip_testonly = '192.168.1.100'
     wvtest.WVPASSEQ(b.get_ip_address(), '192.168.1.100')
 
+    # Not on the subnet; adding IP should fail.
+    wvtest.WVEXCEPT(ValueError, b.set_gateway_ip, '192.168.2.1')
+
   finally:
     shutil.rmtree(tmp_dir)