Systems and methods are described for providing dynamic function calls in an on-demand code execution system, whereby a task can be invoked on the on-demand code execution system based on functionality provided by the task, rather than an identifier of the task. The on-demand code execution system can enable tasks to register as providing a given functionality, and when a call is received to implement the functionality (e.g., from another task on the on-demand code execution system), the on-demand code execution system can select a task based on those registered. In some instances, the selected task may be based on a combination of execution cost of the task (e.g., compute costs utilized to execute the task) and invocation costs of the task (e.g., compute costs utilized to initiate execution of the task on the on-demand code execution system).