Much of what we can do with Computer Science seems like magic, such as searching billions of items in a fraction of a second, or decrypting a secure message without needing to know the key that was used to encrypt it. Other parts are surprising - surely given a fast enough computer we can find the optimal solution to a problem? This talk investigates magical and paradoxical ideas in computer science, and how it relates to Computer Science education.