Some of these answers are pretty old, so maybe it’s changed in recent times, but I had similar issues and I solved it by:
- Loading the USB drivers for the device – Samsung S6
- Enable Developer tools on the phone.
- On the device, go to Settings – Applications – Development – Check USB Debugging
- Reboot O/S (Windows 7 – 64bit)
- Open Visual Studio
I think it was step 3 that had me stumped for a while. I’d enabled developer tools, but I didn’t specifically enable the “USB Debugging” but.