Techniques are described for facilitating interactions between task requesters who have tasks that are available to be performed and task performers who are available to perform tasks, such as by an intermediary electronic marketplace or other task fulfillment facilitator system. In some situations, task performer users and/or other users may create task subscriptions for use in automatically identifying tasks of interest to the users about which the users desire to receive notification. The users may be notified of the identified tasks in various ways, such as by sending electronic messages of various types to the users that include indications of the tasks identified for those users based on their subscriptions. Tasks of interest may be identified in various ways, such as based on task attributes of interest specified for a subscription that are later matched against tasks that are available at the time of the matching.