Visual Studio doesn't discover my unit tests!

I added a unit test class to a project today, and Visual Studio couldn't find my new unit tests. Quick hack: modify your output window to "Show output from:" "Tests." This may help you find the reason why. In my case, it told me pretty directly what the issue was:

UTA001: TestClass attribute defined on non-public class MyTests

My test class wasn't public, which it appears is a requirement for discovery.