Methods, systems, and computer-readable media for distributed computing with adaptive parallelization are disclosed. An execution time metric is determined based (at least in part) on execution of a batch of jobs. A quantity of partitions for an additional batch of jobs is determined based (at least in part) on the execution time metric and on a target metric. The additional batch of jobs is divided between a set of partitions of the determined quantity. Execution is initiated of the additional batch of jobs in the set of partitions. The set of partitions comprises at least a first partition and a second partition. A first subset of jobs in the first partition is executed in parallel with a second subset of jobs in the second partition.