We study Nordhaus–Gaddum problems for Kemeny’s constant K ( G ) of a connected graph G . We prove bounds on min { K ( G ) , K ( G ¯ ) } and the product K ( G ) K ( G ¯ ) for various families of graphs. In particular, we show that if the maximum degree of a graph G on n vertices is n − O ( 1 ) or n − Ω ( n ) , then min { K ( G ) , K ( G ¯ ) } is at most O ( n ) .