The random walk (d)-ary cuckoo hashing algorithm was defined by Fotakis, Pagh, Sanders, and Spirakis to generalize and improve upon the standard cuckoo hashing algorithm of Pagh and Rodler. Random walk (d)-ary cuckoo hashing has low space overhead, guaranteed fast access, and fast in practice insertion time. In this paper, we give a theoretical insertion time bound for this algorithm. More precisely, for every (d\ge 3) random hashes, let (c_d^) be the sharp threshold for the load factor at which a valid assignment of (cm) objects to a hash table of size (m) exists with high probability. We show that for any (d\ge 3) hashes and load factor (c<c_d^), the expectation of the random walk insertion time is (O(1)), that is, a constant depending only on (d) and (c) but not (m).