diff --git a/src/rpc/rawtransaction.cpp b/src/rpc/rawtransaction.cpp
--- a/src/rpc/rawtransaction.cpp
+++ b/src/rpc/rawtransaction.cpp
@@ -318,10 +318,14 @@
             throw JSONRPCError(RPC_INVALID_ADDRESS_OR_KEY, "Block not found");
         pblockindex = mapBlockIndex[hashBlock];
     } else {
-        const Coin &coin = AccessByTxid(*pcoinsTip, oneTxid);
-        if (!coin.IsSpent() && coin.GetHeight() > 0 &&
-            int64_t(coin.GetHeight()) <= chainActive.Height()) {
-            pblockindex = chainActive[coin.GetHeight()];
+        // Loop through txids and try to find which block they're in. Exit loop
+        // once a block is found.
+        for (const auto &tx : setTxids) {
+            const Coin &coin = AccessByTxid(*pcoinsTip, tx);
+            if (!coin.IsSpent()) {
+                pblockindex = chainActive[coin.GetHeight()];
+                break;
+            }
         }
     }
 
@@ -355,7 +359,7 @@
     if (ntxFound != setTxids.size()) {
         throw JSONRPCError(
             RPC_INVALID_ADDRESS_OR_KEY,
-            "(Not all) transactions not found in specified block");
+            "Not all transactions found in specified or retrieved block");
     }
 
     CDataStream ssMB(SER_NETWORK, PROTOCOL_VERSION);
diff --git a/test/functional/merkle_blocks.py b/test/functional/merkle_blocks.py
--- a/test/functional/merkle_blocks.py
+++ b/test/functional/merkle_blocks.py
@@ -47,7 +47,9 @@
             [node0utxos.pop()], {self.nodes[1].getnewaddress(): 49.99})
         txid2 = self.nodes[0].sendrawtransaction(
             self.nodes[0].signrawtransaction(tx2, None, None, "ALL|FORKID")["hex"])
-        assert_raises(JSONRPCException, self.nodes[0].gettxoutproof, [txid1])
+        # This will raise an exception because the transaction is not yet in a block
+        assert_raises_jsonrpc(-5, "Transaction not yet in block",
+                              self.nodes[0].gettxoutproof, [txid1])
 
         self.nodes[0].generate(1)
         blockhash = self.nodes[0].getblockhash(chain_height + 1)
@@ -68,7 +70,7 @@
         txin_spent = self.nodes[1].listunspent(1).pop()
         tx3 = self.nodes[1].createrawtransaction(
             [txin_spent], {self.nodes[0].getnewaddress(): 49.98})
-        self.nodes[0].sendrawtransaction(
+        txid3 = self.nodes[0].sendrawtransaction(
             self.nodes[1].signrawtransaction(tx3, None, None, "ALL|FORKID")["hex"])
         self.nodes[0].generate(1)
         self.sync_all()
@@ -77,23 +79,28 @@
         txid_unspent = txid1 if txin_spent["txid"] != txid1 else txid2
 
         # We can't find the block from a fully-spent tx
-        assert_raises(
-            JSONRPCException, self.nodes[2].gettxoutproof, [txid_spent])
-        # ...but we can if we specify the block
+        assert_raises_jsonrpc(-5, "Transaction not yet in block",
+                              self.nodes[2].gettxoutproof, [txid_spent])
+        # We can get the proof if we specify the block
         assert_equal(self.nodes[2].verifytxoutproof(
             self.nodes[2].gettxoutproof([txid_spent], blockhash)), [txid_spent])
-        # ...or if the first tx is not fully-spent
+        # We can't get the proof if we specify a non-existent block
+        assert_raises_jsonrpc(-5, "Block not found", self.nodes[2].gettxoutproof, [
+                              txid_spent], "00000000000000000000000000000000")
+        # We can get the proof if the transaction is unspent
         assert_equal(self.nodes[2].verifytxoutproof(
             self.nodes[2].gettxoutproof([txid_unspent])), [txid_unspent])
-        try:
-            assert_equal(self.nodes[2].verifytxoutproof(
-                self.nodes[2].gettxoutproof([txid1, txid2])), txlist)
-        except JSONRPCException:
-            assert_equal(self.nodes[2].verifytxoutproof(
-                self.nodes[2].gettxoutproof([txid2, txid1])), txlist)
-        # ...or if we have a -txindex
+        # We can get the proof if we provide a list of transactions and one of them is unspent. The ordering of the list should not matter.
+        assert_equal(sorted(self.nodes[2].verifytxoutproof(
+            self.nodes[2].gettxoutproof([txid1, txid2]))), sorted(txlist))
+        assert_equal(sorted(self.nodes[2].verifytxoutproof(
+            self.nodes[2].gettxoutproof([txid2, txid1]))), sorted(txlist))
+        # We can always get a proof if we have a -txindex
         assert_equal(self.nodes[2].verifytxoutproof(
             self.nodes[3].gettxoutproof([txid_spent])), [txid_spent])
+        # We can't get a proof if we specify transactions from different blocks
+        assert_raises_jsonrpc(-5, "Not all transactions found in specified or retrieved block",
+                              self.nodes[2].gettxoutproof, [txid1, txid3])
 
 
 if __name__ == '__main__':