Men's uptake of HIV testing is critical to the success of "test and treat" strategies in generalized epidemics. This study sought to identify cultural factors and community processes that influence men's HIV testing uptake in the baseline year of an ongoing test-and-treat trial among 334,479 persons in eastern Africa (SEARCH, NCT#01864603). Data were collected using participant observation at mobile community health campaigns (CHCs) (n = 28); focus group discussions (n = 8 groups) with CHC participants; and in-depth interviews with care providers (n = 50), leaders (n = 32), and members (n = 112) of eight communities in Kenya and Uganda. An 8-person research team defined analytical codes and iteratively refined them during data collection using grounded theoretical approaches, and textual data were coded using Atlas.ti software. Structural and cultural barriers, including men's mobility and gender norms valorizing risk-taking and discouraging health-seeking behavior, were observed, and contributed to men's lower participation in HIV testing relative to women. Men's labor opportunities often require extended absences from households: during planting season, men guarded fields from monkeys from dawn until nightfall; lake fishermen traveled long distances and circulated between beaches. Men often tested "by proxy", believing their wives' HIV test results to be their status. Debates about HIV risks were vigorous, with many men questioning "traditional" masculine gender norms that enhanced risks. The promise of antiretroviral therapy (ART) to prolong health was a motivating factor for many men to participate in testing. Flexibility in operating hours of HIV testing including late evening and weekend times along with multiple convenient locations that moved were cited as facilitating factors enhancing male participating in HIV testing. Mobile testing reduced but did not eliminate barriers to men's participation in a large-scale "test & treat" effort. However, transformations in gender norms related to HIV testing and care-seeking are underway in eastern Africa and should be supported.