According to the forum thread I found when experiencing this same problem, it's because Debian is now building mysql with libeditline instead of libreadline, and libeditline does not do ctrl-R by default: http://ubuntuforums.org/showthread.php?t=1147183 I would like to see libreadline used again to build mysql-client