Online social media is changing the personnel recruitment process. Until now, resumes were among the most widely used tools for the screening of job applicants. The advent of inexpensive sensors combined with the success of online video platforms has enabled the introduction of a new type of resume, the video resume. Video resumes can be defined as short video messages where job applicants present themselves to potential employers. Online video resumes represent an opportunity to study the formation of first impressions in an employment context at a scale never achieved before, and to our knowledge they have not been studied from a behavioral standpoint. We collected a dataset of 939 conversational English-speaking video resumes from YouTube. Annotations of demographics, skills, and first impressions were collected using the Amazon Mechanical Turk crowdsourcing platform. Basic demographics were then analyzed to understand the population using video resumes to find a job, and results showed that the population mainly consisted of young people looking for internship and junior positions. We developed a computational framework for the prediction of organizational first impressions, where the inference and nonverbal cue extraction steps were fully automated. Results demonstrated that automatically predicting first impressions up to a certain level was a feasible task, with up to 27% of the variance explained for extraversion, and up to 20% for social and communication skills.