diff --git a/qa/rpc-tests/blockchain.py b/qa/rpc-tests/blockchain.py
--- a/qa/rpc-tests/blockchain.py
+++ b/qa/rpc-tests/blockchain.py
@@ -50,10 +50,36 @@
         assert_equal(res['transactions'], 200)
         assert_equal(res['height'], 200)
         assert_equal(res['txouts'], 200)
-        assert_equal(res['bytes_serialized'], 13924),
+        assert_equal(res['bytes_serialized'], 13924)
+        assert_equal(res['bestblock'], node.getblockhash(200))
         assert_equal(len(res['bestblock']), 64)
         assert_equal(len(res['hash_serialized']), 64)
 
+        self.log.info(
+            "Test that gettxoutsetinfo() works for blockchain with just the genesis block")
+        b1hash = node.getblockhash(1)
+        node.invalidateblock(b1hash)
+
+        res2 = node.gettxoutsetinfo()
+        assert_equal(res2['transactions'], 0)
+        assert_equal(res2['total_amount'], Decimal('0'))
+        assert_equal(res2['height'], 0)
+        assert_equal(res2['txouts'], 0)
+        assert_equal(res2['bestblock'], node.getblockhash(0))
+        assert_equal(len(res2['hash_serialized']), 64)
+
+        self.log.info(
+            "Test that gettxoutsetinfo() returns the same result after invalidate/reconsider block")
+        node.reconsiderblock(b1hash)
+
+        res3 = node.gettxoutsetinfo()
+        assert_equal(res['total_amount'], res3['total_amount'])
+        assert_equal(res['transactions'], res3['transactions'])
+        assert_equal(res['height'], res3['height'])
+        assert_equal(res['txouts'], res3['txouts'])
+        assert_equal(res['bestblock'], res3['bestblock'])
+        assert_equal(res['hash_serialized'], res3['hash_serialized'])
+
     def _test_getblockheader(self):
         node = self.nodes[0]
 
diff --git a/src/txdb.cpp b/src/txdb.cpp
--- a/src/txdb.cpp
+++ b/src/txdb.cpp
@@ -101,7 +101,12 @@
      */
     i->pcursor->Seek(DB_COINS);
     // Cache key of first record
-    i->pcursor->GetKey(i->keyTmp);
+    if (i->pcursor->Valid()) {
+        i->pcursor->GetKey(i->keyTmp);
+    } else {
+        // Make sure Valid() and GetKey() return false
+        i->keyTmp.first = 0;
+    }
     return i;
 }