The COVID-19 pandemic has completely changed the world, and businesses are struggling to create a new and effective working environment for their employees. Employees worldwide have moved from traditional face-to-face meetings to remote working using video conferencing software (VCS)—a powerful tool to support companies during the pandemic and that can be an increasing trend in the future. For businesses who intend to adopt VCS for their organizations, choosing an appropriate platform can be an arduous task that requires the consideration of multiple criteria to save costs and optimize efficiency. In this paper, we propose a grey-based multi-criteria decision making (MCDM) framework that combines grey Analytical Hierarchy Process (G-AHP) and grey Evaluation Based on Distance from Average Solution (G-EDAS) methodologies, in which grey numbers are used to express the linguistic evaluation statements of experts. Initially, the evaluation criteria based on functionality, security, usability, technical performance, and pricing have been determined using a literature review and expert’s opinions to employ the MCDM approach. G-AHP was utilized to identify the criteria weights, and G-EDAS was then used to select the best VCS among the alternatives. A case illustration in Vietnam is presented to exhibit the proposed approach’s applicability. From the G-AHP findings, quality of video/audio, ease of use, mobile experience, number of participants allowed, and video recording capability have been ranked as the five most important criteria. From G-EDAS analysis, Microsoft Teams (VCS-03) was found to be the best. In addition, the robustness of the proposed model was tested by conducting sensitivity analysis and comparative analysis of methods, in which the priority rankings of the best VCSs are very similar. With the high demand for the trend of the remote working model, this study can be a basis for informed decisions to assist businesses in choosing their best-suited VCS to save costs and enhance productivity.