The disclosed computer-implemented method for completing multi-factor authentication via mobile devices may include (1) identifying a request to communicate with a user's mobile device to complete multi-factor authentication of the user to an online service, (2) determining that authentication notifications are disabled for attempts made by the user to login to the online service, (3) preventing an authentication notification from being displayed on the user's mobile device, (4) receiving an out-of-band authentication communication from a mobile device, (5) determining that the mobile device that sent the out-of-band authentication communication is the user's mobile device and is therefore trusted to complete the multi-factor authentication of the user to the online service, and (6) enabling the user to login to the online service and automatically receive future notification. Various other methods, systems, and computer-readable media are also disclosed.