In the submodular welfare maximization (SWM) problem, the input consists of a set of n items, each of which must be allocated to one of m agents. Each agent l has a valuation function vl, where vl(S) denotes the welfare obtained by this agent if she receives the set of items S. The functions vl are all submodular; as is standard, we assume that they are monotone and vl(Φ) = 0. The goal is to partition the items into m disjoint subsets S1; S2, ..., Sm in order to maximize the so-cial welfare, defined as .... A simple greedy algorithm gives a 1/2-approximation to SWM in the offline setting, and this was the best known until Vondrák's recent (1 - 1/e)-approximation algorithm [Optimal approximation for the submodular welfare problem in the value oracle model, in Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (STOC '08), ACM, 2008, pp. 67-74]. In this paper, we consider the online version of SWM. Here, items arrive one at a time in an online manner; when an item arrives, the algorithm must make an irrevocable decision about which agent to assign it to before seeing any subsequent items. This problem is motivated by applications to Internet advertising, where user ad impressions must be allocated to advertisers whose value is a submodular function of the set of users/impressions they receive. There are two natural models that differ in the order in which items arrive. In the fully adversarial setting, an adversary can construct an arbitrary/worst-case instance, as well as pick the order in which items arrive in order to minimize the algorithm's performance. In this setting, the 1/2-competitive greedy algorithm is the best possible. To improve on this, one must weaken the adversary slightly: In the random order model, the adversary can construct a worst-case set of items and valuations but does not control the order in which the items arrive; instead, they are assumed to arrive in a random order. The random order model has been well studied for online SWM and various special cases, but the best known competitive ratio (even for several special cases) is 1/2+1=n, which is barely better than the ratio for the adversarial order [S. Dobzinski, N. Nisan, and M. Schapira, Math. Oper. Res., 35 (2010), pp. 1-13; S. Dobzinski and M. Schapira, An improved approximation algorithm for com-binatorial auctions with submodular bidders, in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '06), ACM; SIAM, 2006, pp. 1064-1073]. Obtaining a competitive ratio of 1/2 + Ω(1) for the random order model has been an important open problem for several years. We solve this open problem by demonstrating that the greedy algorithm has a competitive ratio of at least 0:505 for online SWM in the random order model. This is the first result showing a competitive ratio bounded above 1/2 in the random order model, even for special cases such as the weighted matching or budgeted allocation problem (without the so-called large capac-ity assumptions). For special cases of submodular functions including weighted matching, weighted coverage functions, and a broader class of "second-order supermodular" functions, we provide a different analysis that gives a competitive ratio of 0.51. We analyze the greedy algorithm using a factor-revealing linear program, bounding how the assignment of one item can decrease potential welfare from assigning future items. In addition to our new competitive ratios for online SWM, we make two further contributions: First, we define the classes of second-order modular, supermodular, and submodular functions, which are likely to be of independent interest in submodular optimiza-tion. Second, we obtain an improved competitive ratio via a technique we refer to as gain linearizing, which may be useful in other contexts (see [V. S. Mirrokni and M. Zadimoghaddam, Randomized composable core-sets for distributed submodular maximization, in Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC '15), ACM, 2015, pp. 153-162]): Essen-tially, we linearize the submodular function by dividing the gain of an optimal solution into gain from individual elements, compare the algorithm's gain when it assigns an element to the optimal solution's gain from the element, and, crucially, bound the extent to which assigning elements can affect the potential gain of other elements. [ABSTRACT FROM AUTHOR]